# Python Challenge - Balanced Binary Search Tree

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 () 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.

You can also find further discussion and get answers to your questions over in #get-help.

Agree with a comment or answer? 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

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!

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)

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.

``````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)
``````

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)
``````

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)
# 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)