Trees

BST Insert

Insert values into a binary search tree by comparing at each node.

Algorithm

Basic Implementation

basic.py 
class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def render(node):
    if node is None:
        return "_"
    if node.left is None and node.right is None:
        return str(node.value)
    return f"{node.value}({render(node.left)},{render(node.right)})"

def sample_tree():
    n1 = Node(1)
    n3 = Node(3)
    n2 = Node(2, n1, n3)
    n5 = Node(5)
    n7 = Node(7)
    n6 = Node(6, n5, n7)
    return Node(4, n2, n6)

def insert(root, value):
    if root is None:
        return Node(value)
    if value < root.value:
        root.left = insert(root.left, value)
    else:
        root.right = insert(root.right, value)
    return root
root = None
for value in [4, 2, 6, 1, 3, 5, 7]:
    root = insert(root, value)
print(render(root))

BST insertion is a comparison path. The pinned tree 4(2(1,3),6(5,7)) is shown with the inserted value taking its sorted slot.

Step 1 - Start at root

For value 5, compare with 4 first; 5 is larger, so move right.

First comparison: 5 > 4, so the search for the insert slot goes right.insert 54compare26137

Step 2 - Take the left slot under 6

At 6, value 5 is smaller, so it becomes the left child.

Second comparison: 5 < 6, so the open left slot is used.426compare135new7

Step 3 - Canonical tree

The resulting tree is the pinned shape 4(2(1,3),6(5,7)).

Final BST after 5 is present under 6.4261357

Complexity

  • Time: O(h) per insert
  • Space: O(n)

Implementation notes

  • Python represents each tree node as a Node object with dynamic value, left, and right attributes. root is a reference that starts as None and is rebound to the object returned by insert.
  • insert(root, value) is recursive. A None child allocates Node(value); otherwise the code mutates root.left or root.right with the recursive return value. Because the branch is if value < root.value / else, duplicates would follow the right branch.
  • Python manages allocated nodes while they remain reachable from root and can reclaim them once no references remain. The replay shows the comparison path for each value, the new child link in the rendered tree, and a sorted-order contrast where the same insertion rule forms a height-4 chain.
binary search tree Values smaller than a node go left; larger values go right.