Trees

BST Insert

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

Algorithm

Basic Implementation

Basic.java 
import java.util.*;

public class Basic {
    static class Node {
        int value;
        Node left;
        Node right;
        Node(int value) { this.value = value; }
        Node(int value, Node left, Node right) { this.value = value; this.left = left; this.right = right; }
    }
    static String render(Node node) {
        if (node == null) return "_";
        if (node.left == null && node.right == null) return Integer.toString(node.value);
        return node.value + "(" + render(node.left) + "," + render(node.right) + ")";
    }
    static Node sampleTree() {
        return new Node(4, new Node(2, new Node(1), new Node(3)), new Node(6, new Node(5), new Node(7)));
    }
    static Node insert(Node root, int value) { if (root == null) return new Node(value); if (value < root.value) root.left = insert(root.left, value); else root.right = insert(root.right, value); return root; }
    public static void main(String[] args) { Node root = null; for (int value : new int[] {4, 2, 6, 1, 3, 5, 7}) root = insert(root, value); System.out.println(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

  • Java represents each tree node as a Node object with primitive int value plus Node left and Node right reference fields. Missing children are null.
  • main starts with Node root = null and reassigns root = insert(root, value) for each value, so the first root == null case can return the new root object.
  • insert is recursive: a null subtree allocates new Node(value); value < root.value assigns root.left = insert(root.left, value); otherwise root.right = insert(root.right, value). Equal values would follow the right branch because there is no separate duplicate case.
  • The replay exposes each comparison path and rendered tree state, ending with 4(2(1,3),6(5,7)); it also keeps the sorted-insert contrast 1(_,2(_,3(_,4))) to show the unbalanced O(n) path. Allocated nodes are ordinary JVM heap objects managed by GC.
binary search tree Values smaller than a node go left; larger values go right.