BST Add Child

Whiteboard: Harder
Challenge: Medium
Concepts: BST, Recursion
Download: bst-add-child.zip
Solution: BST Add Child: Solution

In this challenge, you will write a function to append a child to a node in a Binary Search Tree.

We’ll give you a Node class with left and right attributes, as well as a data attribute:

bstadd.py

class Node(object):  # ...
    def __init__(self, data, left=None, right=None):
        """Create node, with data and optional left/right."""

        self.left = left
        self.right = right
        self.data = data

Consider this tree:

We can build this tree using our Node class like this:

>>> t = Node(4,
...       Node(2, Node(1), Node(3)),
...       Node(7, Node(5), Node(8))
... )

If we wanted to add 0 to our tree, it would end up as the left-most child of our tree, as it comes before everything else in the tree. We’d end up with this tree:

Our insert method should do this correctly:

>>> t.insert(0)

>>> t.left.left.left.data == 0
True

>>> t.left.left.right is None
True

If we added 9, it would end up as the right-most node, as it comes after everything else in the tree:

Our insert method should do this correctly:

>>> t.insert(9)

>>> t.right.right.right.data == 9
True

>>> t.right.right.left is None
True

If we added 6, it would end up to the right of the 5:

Our insert method should do this correctly:

>>> t.insert(6)

>>> t.right.left.right.data == 6
True

>>> t.right.left.left is None
True

We’ve given you a stub of the insert method:

bstadd.py

class Node(object):  # ...
    def insert(self, new_data):
        """Insert new node with `new_data` to BST tree rooted here."""

Implement it.

It may help to practice adding a few nodes by hand to a tree to figure out the pattern for where to add a node.

Duplicate Entries

There are different ways to deal with duplicate entries in a binary tree. Some trees use a rule that allows for equality, like “if the value is less than the current value, go left” and “if the value is greater than or equal to the current value, go right”.

For this code challenge, you do not have to deal with duplicate values; you may assume that every item inserted into the tree is unique.

Balanced Binary Search Trees

A “balanced” binary search tree is one where the nodes are equitably spread out to guarantee O(log n) search. For this code challenge, you should not try to re-arrange the tree to rebalance it after adding an item; instead, you should simply find the correct place in the current tree to add it.

Rebalancing trees is an interesting advanced topic. You can consult a good algorithms book on “AVL Trees” for an introduction.