Python Challenge - Balanced Binary Search Tree

Frequently Asked Questions
1

Community%20FAQs%20on%20Codecademy%20Exercises
Community%20FAQs%20on%20Codecademy%20Exercises1000×208 141 KB

This community-built FAQ covers the “Balanced Binary Search Tree” code challenge in Python. You can find that challenge here, or pick any challenge you like from our list.

Top Discussions on the Python challenge Balanced Binary Search Tree

There are currently no frequently asked questions or top answers associated with this challenge – that’s where you come in! You can contribute to this section by offering your own questions, answers, or clarifications on this challenge. Ask a question or post a solution by clicking reply (reply) below.

If you’ve had an “aha” moment about the concepts, formatting, syntax, or anything else with this challenge, consider sharing those insights! Teaching others and answering their questions is one of the best ways to learn and stay sharp.

Join the Discussion. Help a fellow learner on their journey.

Ask or answer a question about this exercise by clicking reply (reply) below!
You can also find further discussion and get answers to your questions over in #get-help.

Agree with a comment or answer? Like (like) to up-vote the contribution!

Need broader help or resources? Head to #get-help and #community:tips-and-resources. If you are wanting feedback or inspiration for a project, check out #project.

Looking for motivation to keep learning? Join our wider discussions in #community

Learn more about how to use this guide.

Found a bug? Report it online, or post in #community:Codecademy-Bug-Reporting

Have a question about your account or billing? Reach out to our customer support team!

None of the above? Find out where to ask other questions here!

2
class TreeNode(): def __init__(self, value): self.right = None self.left = None self.value = value def __str__(self): return f"{self.value}->{self.left}\n{self.value}->{self.right}" def balanced_bst(a): if len(a) < 1: return None else: root = TreeNode(a[len(a)//2]) root.left = balanced_bst(a[:len(a)//2]) root.right = balanced_bst(a[len(a)//2 + 1:]) return root a = [1,2,3,4,5,6,7,8] balanced_node = balanced_bst(a) print(balanced_node)
3

I used recursion and array slicing, like the previous post.
I made finding the middle index a separate function.
And I added some methods to the TreeNode class.

my code 
from math import ceil, floor

class TreeNode():
  def __init__(self, value):
    self.right = None
    self.left = None
    self.value = value
  
  def __str__(self):
    return f"{self.value}->{self.left}\n{self.value}->{self.right}"
  
  def bi_str(self):
    bi = ""
    if (self.left is not None):
      bi += str(self.left.value) + "<-"
    bi += "(" + str(self.value) + ")"
    if (self.right is not None):
      bi += "->" + str(self.right.value)
    return bi

  def search(self, value):
    if value < self.value:
      if self.left is not None:
        return self.left.search(value)
    elif value > self.value:
      if self.right is not None:
        return self.right.search(value)
    elif value == self.value:
      return self
    return None


def get_middle_index(ls, useLower = False):
  mid = (len(ls) - 1) / 2
  if (useLower):
    return floor(mid)
  else:
    return ceil(mid)

def balanced_bst(a):
  n = len(a) # n is length

  # base cases for recursion: n = 0, 1, 2, 3
  if n == 0:
    return None
  if n == 1:
    return TreeNode(a[0])
  elif n == 2:
    node = TreeNode(a[1])
    node.left = TreeNode(a[0])
    return node
  elif n == 3:
    node = TreeNode(a[1])
    node.left = TreeNode(a[0])
    node.right = TreeNode(a[2])
    return node
  
  # recursive case
  else:
    mid = get_middle_index(a, False)
    node = TreeNode(a[mid])
    node.left = balanced_bst(a[:mid])
    node.right = balanced_bst(a[mid+1:])
    return node


d = [1,2,3,4,5,6,7,8]
balanced_node = balanced_bst(d)
print(balanced_node)

print()
for x in d:
  print(balanced_node.search(x).bi_str())

I probably could have left out some of those base cases,
and I could have used integer division // instead of math.floor and math.ceil.

My code is long.

4 
class TreeNode():
  def __init__(self, value):
    self.right = None
    self.left = None
    self.value = value
  
  def __str__(self):
    return f"{self.value}->{self.left}\n{self.value}->{self.right}"

def balanced_bst(a):
  if len(a) == 0:
    return None
  else:
    mid = len(a) // 2
    root = TreeNode(a[mid])
    root.left = balanced_bst(a[:mid])
    root.right = balanced_bst(a[mid+1:])
    return root

a = [1,2,3,4,5,6,7,8]
balanced_node = balanced_bst(a)
print(balanced_node)
5

Looks like I did some checks I didn’t need but here is my answer.

class TreeNode():
  def __init__(self, value):
    self.right = None
    self.left = None
    self.value = value
  
  def __str__(self):
    return f"{self.value}->{self.left}\n{self.value}->{self.right}"


def balanced_bst(a):
  mid = len(a) // 2
  print(a)
  if not a:
    return None
  elif a:
    node = TreeNode(a[mid])
    if len(a) == 1:
      return TreeNode(a[0])
    elif len(a) > 1:
      node.left = balanced_bst(a[:mid])
      node.right = balanced_bst(a[(mid+1):])
  return node

a = [1,2,3,4,5,6,7,8]
balanced_node = balanced_bst(a)
print(balanced_node)
6

Here is my naive recursive version, glad I found a similar approach to others:

class TreeNode(): def __init__(self, values): self.right,self.left,self.value = None, None, None if len(values) == 1: self.value = values[0] elif len(values) > 1: midpt = len(values)//2 self.value = values[midpt] self.right = TreeNode(values[midpt+1:]) self.left = TreeNode(values[:midpt]) def __str__(self): return f"{self.value}->{self.left}\n{self.value}->{self.right}" def balanced_bst(a): if not a: return None return TreeNode(a) a = [1,2,3,4,5,6,7,8,9] balanced_node = balanced_bst(a) print(balanced_node)
7
# A class to store a BST node class TreeNode(): def __init__(self, value): self.right = None self.left = None self.value = value def __str__(self): return f"{self.value}->{self.left}\n{self.value}->{self.right}" # Function to construct balanced BST from the given sorted list def construct(keys, low, high, root): # base case if low > high: return root # find the middle element of the current range mid = (low + high) // 2 # construct a new node from the middle element and assign it to the root root = TreeNode(keys[mid]) # left subtree of the root will be formed by keys less than middle element root.left = construct(keys, low, mid - 1, root.left) # right subtree of the root will be formed by keys more than the middle element root.right = construct(keys, mid + 1, high, root.right) return root # Function to construct balanced BST from the givenn unsorted list (a) def balanced_bst(a): # sort the keys first a.sort() # construct a balanced BST and return the root node of the tree return construct(a, 0, len(a) - 1, None) if __name__ == '__main__': # input keys a = [1,2,3,4,5,6,7,8] # construct a balanced binary search tree balanced_node = balanced_bst(a) # print the keys in an inorder fashion print(balanced_node)
8

class TreeNode():
def init(self, value):
self.right = None
self.left = None
self.value = value

def str(self):
return f"{self.value}->{self.left}\n{self.value}->{self.right}"

def balanced_bst(a):
return constructBst(a, 0, len(a) - 1)

def constructBst(array, startIdx, endIdx):
if startIdx > endIdx:
return None

midIdx = (startIdx + endIdx) // 2
bst = TreeNode(array[midIdx])

bst.left = constructBst(array, startIdx, midIdx - 1)
bst.right = constructBst(array, midIdx + 1, endIdx)

return bst

10 
class TreeNode():
  def __init__(self, value):
    self.right = None
    self.left = None
    self.value = value
  
  def __str__(self):
    return f"{self.value}->{self.left}\n{self.value}->{self.right}"


def balanced_bst(a):
  return constructBst(a, 0, len(a) - 1)

def constructBst(array, startIdx, endIdx):
  if startIdx > endIdx:
    return None

  midIdx = (startIdx + endIdx) // 2
  bst = TreeNode(array[midIdx])

  bst.left = constructBst(array, startIdx, midIdx - 1)
  bst.right = constructBst(array, midIdx + 1, endIdx)

  return bst
11
class TreeNode(): def __init__(self, value): self.right = None self.left = None self.value = value def __str__(self): return f"{self.value}->{self.left}\n{self.value}->{self.right}" def balanced_bst(a): if len(a) < 1: return None else: root_node = TreeNode(a[len(a)//2]) root_node .left = balanced_bst(a[:len(a)//2]) root_node .right = balanced_bst(a[len(a)//2 + 1:]) return root_node a = [1,2,3,4,5,6,7,8] balanced_node = balanced_bst(a) print(balanced_node)
12 
def balanced_bst(a):
  # Write your code here
  if len(a) == 0:
    return None
  index = int(len(a)/2)
  root = TreeNode(a[index])
  root.right = balanced_bst(a[index+1:])
  root.left = balanced_bst(a[:index-1])
  return root