Trees and Binary Search Trees for Interviews

Interviewers expect you to walk a binary tree in all four orders, explain that a balanced binary search tree gives O(log n) search, insert and delete while an unbalanced one degrades to O(n), and state recursion's O(h) stack cost. Most tree questions then reduce to one recursive function over a node's children.

Operations and what they cost

Operation	Balanced BST	Unbalanced BST	Plain binary tree
Search for a value	O(log n)	O(n) at worst	O(n)
Insert	O(log n)	O(n) at worst	n/a, no order to keep
Delete	O(log n)	O(n) at worst	n/a, no order to keep
Smallest or largest value	O(log n)	O(n) at worst	O(n)
Visit every node	O(n)	O(n)	O(n)
Stack space when recursive	O(log n)	O(n) at worst	O(h)

h is the height, the longest path from the root down. Everything in a BST costs O(h), and the difference between the columns is what h is: about log n when balanced, up to n when not. Inserting already-sorted values into a plain BST builds a straight line.

The four traversals, and what each is for

Order	Visits	Reach for it when
Pre-order	Node, left, right	A parent has to be handled before its children: copying a tree or passing values down.
In-order	Left, node, right	You want a BST's values in sorted order, or the kth smallest.
Post-order	Left, right, node	A node's answer needs its children's answers: heights, sizes, subtree totals.
Level-order	One level at a time	The question is about levels, or the shallowest something. It uses a queue.

The BST rule is stronger than it first looks: every value in a node's left subtree is smaller than the node, and every value in its right subtree is larger, not just its direct children. That is what lets search skip a whole subtree at each step, and it is why an in-order walk comes out sorted.

When to reach for it

The data is a hierarchy: folders, org charts, comment threads, parsed expressions.
You need sorted order as well as fast updates, which a hash map cannot give you.
You need range queries: the first value at or above x, or everything between two values.
The question mentions depth, height, paths, ancestors or subtrees.

What your language gives you

Interview code usually writes its own node class, because the question is about the tree. For a sorted map in real code, the languages differ a lot.

Language	What to use	What the documentation says
Java	`TreeMap`, `TreeSet`	TreeMap is "Red-Black tree based," with guaranteed log(n) for containsKey, get, put and remove.
C++	`std::map`, `std::set`	cppreference says logarithmic search, removal and insertion, usually implemented as red-black trees.
Python	A sorted list with `bisect`	The standard library has no balanced tree. bisect's insort is O(n), because the search is dominated by the insertion.
JavaScript	A sorted array	The language has no built-in tree. Say that you would write one or use a library, and state its cost.

How it looks in Python, JavaScript and Java

The same three functions in each language: insert, search and an in-order walk.

class Node:
    def __init__(self, val):
        self.val, self.left, self.right = val, None, None

def insert(root, val):
    if root is None:
        return Node(val)
    if val < root.val:
        root.left = insert(root.left, val)
    elif val > root.val:
        root.right = insert(root.right, val)
    return root                     # a value already present is left alone

def contains(root, val):
    while root:
        if val == root.val:
            return True
        root = root.left if val < root.val else root.right
    return False

def in_order(root, out=None):
    out = [] if out is None else out
    if root:
        in_order(root.left, out)
        out.append(root.val)
        in_order(root.right, out)
    return out

JavaScript

class Node {
  constructor(val) { this.val = val; this.left = null; this.right = null; }
}

function insert(root, val) {
  if (root === null) return new Node(val);
  if (val < root.val) root.left = insert(root.left, val);
  else if (val > root.val) root.right = insert(root.right, val);
  return root;
}

function contains(root, val) {
  while (root !== null) {
    if (val === root.val) return true;
    root = val < root.val ? root.left : root.right;
  }
  return false;
}

function inOrder(root, out = []) {
  if (root !== null) {
    inOrder(root.left, out);
    out.push(root.val);
    inOrder(root.right, out);
  }
  return out;
}

Java

import java.util.*;

class Bst {
    static class Node {
        int val;
        Node left, right;
        Node(int val) { this.val = val; }
    }

    static Node insert(Node root, int val) {
        if (root == null) return new Node(val);
        if (val < root.val) root.left = insert(root.left, val);
        else if (val > root.val) root.right = insert(root.right, val);
        return root;
    }

    static boolean contains(Node root, int val) {
        while (root != null) {
            if (val == root.val) return true;
            root = val < root.val ? root.left : root.right;
        }
        return false;
    }

    static void inOrder(Node root, List<Integer> out) {
        if (root == null) return;
        inOrder(root.left, out);
        out.add(root.val);
        inOrder(root.right, out);
    }
}

How to explain the choice out loud

What a strong candidate might say

I'll use a binary search tree, because I need the values in sorted order and also fast inserts, and a hash map would lose the order. Each comparison rules out a whole subtree, so search and insert cost O(h), where h is the height. That's O(log n) if the tree stays balanced, but sorted input into a plain BST would make it a line and O(n), so in production I'd use a self-balancing tree like Java's TreeMap. An in-order walk then gives me the sorted values in O(n).

Common mistakes

Claiming O(log n) without saying the tree is balanced.
Checking a node only against its direct children, when the range has to flow down from every ancestor.
Forgetting that a recursive solution uses O(h) stack space, even with no other memory.
Deleting a BST node with two children by removing it outright. Replace it with its in-order successor or predecessor first.
Not saying what happens to duplicates. Decide whether they are ignored or go to one side.

Where to go next

Patterns: tree patterns for recursion and level order, and tries for strings.
Worked problems: Resolve Inherited Folder Permissions and Match an Address Against a List of IP Ranges.
All the figures in one place: the Big O cheat sheet.
Practice saying it: a coding mock interview.