Insertion into Binary Search Tree

Question

So i have to insert a node into a binary search tree. In my introductory class, the binary search trees are represented as linked lists such as , [4, [5, [0, [],[]], [2, [], []]], [1, [],[]]] for this binary tree in the picture below:

this binary tree.

(This is not a binary search tree, just a binary tree that I had a picture of).

So to insert a node into a tree I wrote the following recursive code:

def tree_node(key):
 return [key, [],[]]
def insert(bst,key):
 if bst == []:
 return tree_node(key)
 if key < bst[0]:
 return insert(bst[1],key)
 else:
 return insert(bst[2],key)
 return bst

This just returns the node though, not the new tree with the node

For example:

>>> insert([2, [1, [], []], [3, [], []]], 6)
[6, [], []]

when it should be:

>>> insert([2, [1, [], []], [3, [], []]], 6)
[2, [1, [], []], [3, [], [6, [], []]]]

Thanks!

• Ganesh Datta: You are never inserting the node into your tree. Look at your base case - instead of inserting the node where it should be, you are simply returning the node.

Answer 1

You need to change your base case. Instead of returning a new list, you need to modify the empty list you were passed in. A slice-assignment might be easiest:

def insert(bst,key):
 if bst == []:
 bst[:] = tree_node(key)
 elif key < bst[0]:
 insert(bst[1],key)
 else:
 insert(bst[2],key)

Since this function modifies the tree in place, I'm not returning it. If you want that, just re-add the return bst at the end (but not in recursive steps, we want to ignore those return values).

• Ganesh Datta: Just to clarify to Samrose because he seems to be new to Python - since values are passed by reference, bst[:] = x essentially says replace the values from beginning to end inside the list that bst refers to, with the values found in x. So, in this case, the recursive function finds the leaf node in the bst, and replaces the empty leaf node that was found with the new tree_node being generated by tree_node.
• Blckknght: I'd correct that it replaces the contents of the list (which is empty, so it's not actually removing anything) with the new node's contents. It doesn't rebind any variable names.
• user5995400: @Blckknght Thanks so much! I knew that line was the problem, but I couldn't think of a way to insert it. This works perfectly and makes sense.

Answer 2

Change return insert(bst[1],key) with bst[1] = insert(bst[1],key) (and similarly for bst[2]); this way you are actually inserting something, and will execute the final return statement.