Trees · routine

Insert into a search tree

Write insert(root, value) that adds value to a binary search tree in place and returns the root (a new TreeNode if the tree was empty). Values are all different.

Walk down as if searching; where the search would fall off, hang the new node.

right answers
arguments left as they should be

Already written for you — you can use these

1class TreeNode:
2    def __init__(self, value, left=None, right=None):
3        self.value = value
4        self.left = left
5        self.right = right
6 
7def bst(values):
8    """A balanced binary search tree holding the sorted values."""
9    if not values:
10        return None
11    mid = len(values) // 2
12    return TreeNode(values[mid], bst(values[:mid]), bst(values[mid + 1:]))

def insert(root, value):
    return TreeNode(value, root)

Run adds print(root.right.left.value) after your code, to try it.

Stuck on the idea rather than the code? The Building and walking trees lesson walks through it.