Python - implementing binary tree using recursion

Question

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.

the question is to take in a sorted list as an argument for a function that creates a binary tree using recursion — atomic-coder
– atomic-coder, Commented Oct 26, 2021 at 17:24

trincot · Accepted Answer · 2021-10-26 19:06:21Z

1

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):])
  }

answered Oct 26, 2021 at 19:06

trincot

357k38 gold badges282 silver badges338 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Python - implementing binary tree using recursion

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related