Trees and Binary Search Trees

Tree questions are popular because they test recursion, and recursion tests how clearly you think. The trick is the same every time: decide what a function should return for one node, trust it for the children, and handle the empty tree. Learn that pattern here and most tree problems become short.

1. What are the tree traversals? Write them.

Depth-first: preorder (node, left, right), inorder (left, node, right) and postorder (left, right, node). Breadth-first: level order, using a queue. Inorder on a BST gives sorted output — interviewers love that fact.

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

2. Find the height (maximum depth) of a binary tree.

The height of an empty tree is 0; otherwise it is one more than the taller child. Time O(n), space O(h) for the recursion stack.

int height(Node n) {
    if (n == null) return 0;
    return 1 + Math.max(height(n.left), height(n.right));
}

3. What is a binary search tree? How fast are its operations?

In a BST every node's left subtree holds smaller keys and the right subtree larger keys. Search, insert and delete take O(h): O(log n) when balanced, but O(n) if you insert sorted data and the tree becomes a linked list. Self-balancing trees (AVL, red-black) keep h at O(log n); Java's TreeMap uses a red-black tree.

4. How do you check whether a binary tree is a valid BST?

Checking only each node against its direct children is the classic mistake. Pass down the allowed range instead: everything in the left subtree must stay below the current node, everything in the right above it.

boolean isBst(Node n, long low, long high) {
    if (n == null) return true;
    if (n.val <= low || n.val >= high) return false;
    return isBst(n.left, low, n.val) && isBst(n.right, n.val, high);
}
// call: isBst(root, Long.MIN_VALUE, Long.MAX_VALUE)

5. Print a tree level by level.

Use a queue (BFS). Process the queue size at the start of each round to know where a level ends.

List<List<Integer>> levels(Node root) {
    List<List<Integer>> res = new ArrayList<>();
    if (root == null) return res;
    Deque<Node> q = new ArrayDeque<>(List.of(root));
    while (!q.isEmpty()) {
        int size = q.size();
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            Node n = q.poll();
            level.add(n.val);
            if (n.left != null)  q.add(n.left);
            if (n.right != null) q.add(n.right);
        }
        res.add(level);
    }
    return res;
}

6. Find the lowest common ancestor of two nodes.

In a plain binary tree: if the current node is one of the targets, return it; otherwise search both sides. If both sides return something, the current node is the LCA. In a BST it is simpler — walk down until the two values split to different sides.

Node lca(Node n, Node p, Node q) {
    if (n == null || n == p || n == q) return n;
    Node left = lca(n.left, p, q), right = lca(n.right, p, q);
    return left != null && right != null ? n : (left != null ? left : right);
}

7. What is a heap, and where is it used?

A binary heap is a complete binary tree where each parent is smaller (min-heap) or larger (max-heap) than its children, stored compactly in an array. Peeking at the top is O(1); insert and remove are O(log n). It powers priority queues, Dijkstra's algorithm, scheduling and “top K” problems.

// K largest numbers with a min-heap of size k: O(n log k)
PriorityQueue<Integer> heap = new PriorityQueue<>();
for (int x : nums) {
    heap.offer(x);
    if (heap.size() > k) heap.poll();
}

8. What is a trie and when is it better than a hash map?

A trie stores strings character by character, so words with a common prefix share a path. Lookup costs O(length of word) regardless of how many words are stored, and it answers prefix questions (“all words starting with pro”) that a hash map cannot. It is used in autocomplete, spell checkers and IP routing.