Binary search tree

How does Binary search tree work?

Every node splits its own subtree in two. Everything left is smaller, everything right is larger.

A search compares the target against the current node. That comparison picks one child and drops the other.

An insert walks the same path down. The new node becomes a child of the last node reached.

The rule covers whole subtrees, not just direct children. A left grandchild still has to be smaller than the root.

An in-order traversal reads the values in sorted order. That is the property most problems lean on.

Sorted input builds one long chain. Every operation then costs n, and balancing is the fix.

Sources: Wikipedia: Binary search tree

1. root = 5Inserting 5, 3, 8 and 4. The first value becomes the root.
2. 3 goes left3 is smaller than 5. It becomes the left child.
3. 8 goes right8 is larger than 5. It becomes the right child.
4. 4 goes left, then right4 is smaller than 5, then larger than 3.
5. in-order: 3, 4, 5, 8Reading in order gives the values sorted.

function insert(node, val) {
    if (!node) return { val, left: null, right: null };
    if (val < node.val) node.left = insert(node.left, val);
    else if (val > node.val) node.right = insert(node.right, val);
    return node;
}

interface TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
}

function insert(node: TreeNode | null, val: number): TreeNode {
    if (!node) return { val, left: null, right: null };
    if (val < node.val) node.left = insert(node.left, val);
    else if (val > node.val) node.right = insert(node.right, val);
    return node;
}

def insert(node, val):
    if not node:
        return TreeNode(val)
    if val < node.val:
        node.left = insert(node.left, val)
    elif val > node.val:
        node.right = insert(node.right, val)
    return node

function insert(?TreeNode $node, int $val): TreeNode {
    if ($node === null) return new TreeNode($val);
    if ($val < $node->val) $node->left = insert($node->left, $val);
    elseif ($val > $node->val) $node->right = insert($node->right, $val);
    return $node;
}

    public static TreeNode insert(TreeNode node, int val) {
        if (node == null) {
            TreeNode fresh = new TreeNode();
            fresh.val = val;
            return fresh;
        }
        if (val < node.val) node.left = insert(node.left, val);
        else if (val > node.val) node.right = insert(node.right, val);
        return node;
    }

    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;
    }

    public static TreeNode Insert(TreeNode node, int val) {
        if (node == null) return new TreeNode { val = val };
        if (val < node.val) node.left = Insert(node.left, val);
        else if (val > node.val) node.right = Insert(node.right, val);
        return node;
    }

    public class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;
    }

A worked example of Binary search tree

Check that a tree is a search tree

Decide whether a binary tree obeys the search tree rule.

Every value in the left subtree must be smaller. Every value on the right must be larger.

Comparing a node against its two children is not enough.

Carry a low and a high bound down the tree instead. Each step tightens one of the two.

function isValidBST(root, low = -Infinity, high = Infinity) {
    if (!root) return true;

    // the bound comes from an ancestor, not from the parent alone
    if (root.val <= low || root.val >= high) return false;

    return isValidBST(root.left, low, root.val)
        && isValidBST(root.right, root.val, high);
}

When should you use Binary search tree?

Use Binary search tree when the problem statement says “binary search tree: left < node < right at every node”, “insert/delete/search while keeping the data ordered” or “validate BST / kth smallest / inorder traversal gives sorted order”. A solution built on it usually runs in O(log n) avg.

• •binary search tree: left < node < right at every node
• •insert/delete/search while keeping the data ordered
• •validate BST / kth smallest / inorder traversal gives sorted order
• •closest value or range query on a set that changes over time
• •no array given up front, values arrive one at a time

The signal words of every pattern sit in one table, the algorithm patterns cheat sheet.

What is Binary search tree confused with?

Binary search tree is most often confused with Binary search (array), Hash set / map, Binary heap / priority queue and Tree traversal.

• Binary search (array): An array halves by index but cannot take a cheap insert. A tree halves by pointer and can.
• Hash set / map: A map is faster for an exact lookup. A tree also answers ranges and gives sorted order.
• Binary heap / priority queue: A heap only promises the smallest value at the root. A search tree orders every pair of nodes.
• Tree traversal: That page is about visiting a whole tree. This one is about the ordering rule.

Common mistakes with Binary search tree

• Checking only the direct children

  A deep node can break the rule against a distant ancestor. Pass bounds down instead.

• Assuming the tree is balanced

  Sorted inserts build a chain, not a tree. Then log n is really n.

• Leaving duplicates undecided

  The problem has to say which side a repeated value goes. Pick a side and hold to it.

• Deleting a node with two children carelessly

  A node with two children is replaced by its in-order successor. Any other node breaks the ordering.

Which interview problems use Binary search tree?

Interview problems solved with Binary search tree include Validate binary search tree, Search in a BST, Insert into a BST, Delete node in a BST, Kth smallest element in a BST, Lowest common ancestor of a BST and Convert sorted array to a BST.

• Validate binary search tree: Carry a low and a high bound down.
• Search in a BST: One comparison drops half the tree.
• Insert into a BST: Walk down and hang the node off the last one.
• Delete node in a BST: Replace it with its in-order successor.
• Kth smallest element in a BST: Stop the in-order walk after k nodes.
• Lowest common ancestor of a BST: The first node that sits between the two values.
• Convert sorted array to a BST: The middle element becomes the root, then recurse.

What is the time and space complexity of Binary search tree?

The target complexity of Binary search tree is O(log n) avg.

Balanced, n up to 1e6 gives O(log n) per operation. Unbalanced, the same tree degrades to O(n).