CODEWITHSUNDEEP
pythonrecursionbinary-tree
atomic-coder
atomic-coder

Reputation: 23

Python - implementing binary tree using recursion

def build_bst(l):
  if len(l) == 1:
    return l
  mid = len(l) // 2
  return bst = {'data': l[mid]}, bst["left_child"] == {'data': build_bst(l[:mid])}, bst["right_child"] == {'data': build_bst(l[(mid+1):])}
  

sorted_list = [12, 13, 14, 15, 16]
binary_search_tree = build_bst(sorted_list)
print(binary_search_tree)

Error:

File "recursion.py", line 6
    return bst = {'data': l[mid]}, bst["left_child"] == {'data': build_bst(l[:mid])}, bst["right_child"] == 
{'data': build_bst(l[(mid+1):])}
                       ^
SyntaxError: invalid syntax

Can someone explain what is wrong with my code, I can't seem to find the mistake.

Upvotes: 1

Views: 61

Answers (1)

trincot
trincot

Reputation: 351228

The main issues are:

  • You cannot use = in a return statement -- this is what the error message is about; You should first perform the assignments in separate statements, and then perform the return. Or, use one dictionary literal without any variable assignment.
  • The base case returns an array, but you would expect a BST (dictionary) as return value. Actually, the base case should be when the length of the list is zero
  • The return value of the recursive call is assigned to a data attribute, but the data attribute should get the integer value only, not a BST (dictionary)

Here is a corrected version:

def build_bst(l):
  if not l:
      return None
  mid = len(l) // 2
  return {
      "data": l[mid],
      "left_child": build_bst(l[:mid]),
      "right_child": build_bst(l[(mid+1):])
  }

Upvotes: 1

Related Questions