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 (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 Language Help.

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

Need broader help or resources? Head to Language Help and Tips and Resources. If you are wanting feedback or inspiration for a project, check out Projects.

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

1 Like
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)

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

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

I had chatgpt edit the str method to look a little better.
Still not perfect… but works. added some numers to a to help visually.

class TreeNode(): def __init__(self, value): self.right = None self.left = None self.value = value def __str__(self, depth=0, prefix=""): indent = " " * depth tree_str = "" if self.right: tree_str += self.right.__str__(depth + 1, "/ ") + "\n" tree_str += indent + prefix + str(self.value) + "\n" if self.left: tree_str += self.left.__str__(depth + 1, "\\ ") + "\n" return tree_str def balanced_bst(a): # Write your code here if len(a) == 0: return None if len(a) == 1: return TreeNode(a[0]) mid = len(a)//2 right = mid + 1 root = TreeNode(a[mid]) root.left = balanced_bst(a[:mid]) root.right = balanced_bst(a[right:]) return root a = [1,2,3,4,5,6,7,8,9,10,11] for n in range(12, 30): a.append(n) balanced_node = balanced_bst(a) print(balanced_node)

class TreeNode:
# TreeNode sınıfı başlatılırken değer, sol ve sağ çocuklar için parametreler alır.
def init(self, value=0, left=None, right=None):
self.value = value
self.left = left
self.right = right

# TreeNode objesini yazdırmak için özel bir __str__ metodu.
# Bu, ağacın temel bir görsel temsilini sağlar.
def __str__(self):
    lines, *_ = self._display_aux()
    return '\n'.join(lines)

# Ağacın görsel temsilini oluşturmak için yardımcı bir metod.
def _display_aux(self):
    # Bu metod, ağacın her düzeyini uygun şekilde formatlayarak görselleştirir.
    
    # Eğer düğüm yapraksaysa (yani çocukları yoksa)
    if self.right is None and self.left is None:
        line = '%s' % self.value
        width = len(line)
        height = 1
        middle = width // 2
        return [line], width, height, middle

    # Eğer sadece sol çocuğu varsa
    if self.right is None:
        lines, n, p, x = self.left._display_aux()
        s = '%s' % self.value
        u = len(s)
        first_line = (x + 1) * ' ' + (n - x - 1) * '_' + s
        second_line = x * ' ' + '/' + (n - x - 1 + u) * ' '
        shifted_lines = [line + u * ' ' for line in lines]
        return [first_line, second_line] + shifted_lines, n + u, p + 2, n + u // 2

    # Eğer sadece sağ çocuğu varsa
    if self.left is None:
        lines, n, p, x = self.right._display_aux()
        s = '%s' % self.value
        u = len(s)
        first_line = s + x * '_' + (n - x) * ' '
        second_line = (u + x) * ' ' + '\\' + (n - x - 1) * ' '
        shifted_lines = [u * ' ' + line for line in lines]
        return [first_line, second_line] + shifted_lines, n + u, p + 2, u // 2

    # Eğer iki çocuğu da varsa
    left, n, p, x = self.left._display_aux()
    right, m, q, y = self.right._display_aux()
    s = '%s' % self.value
    u = len(s)
    first_line = (x + 1) * ' ' + (n - x - 1) * '_' + s + y * '_' + (m - y) * ' '
    second_line = x * ' ' + '/' + (n - x - 1 + u + y) * ' ' + '\\' + (m - y - 1) * ' '
    if p < q:
        left += [n * ' '] * (q - p)
    elif q < p:
        right += [m * ' '] * (p - q)
    zipped_lines = zip(left, right)
    lines = [first_line, second_line] + [a + u * ' ' + b for a, b in zipped_lines]
    return lines, n + m + u, max(p, q) + 2, n + u // 2

def balanced_bst(a):
# Eğer liste boşsa, None döndür.
if not a:
return None
# Listenin orta noktasını bul (bu, ağacın kök düğümü olacak).
mid = len(a) // 2
root = TreeNode(a[mid])
# Dizinin sol yarısını kullanarak sol alt ağacı oluştur.
root.left = balanced_bst(a[:mid])
# Dizinin sağ yarısını kullanarak sağ alt ağacı oluştur.
root.right = balanced_bst(a[mid+1:])
# Oluşturulan kök düğümü döndür.
return root

Örnek kullanım

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