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.

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;
}

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?

These phrases in a problem statement point here:

• •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

What is Binary search tree confused with?

• 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

  Its replacement is the in-order successor. Any other node breaks the ordering.

Which interview problems use Binary search tree?

• 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?

O(log n) avg

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