Find a value in a BST

The problem, simply

You get a tree of numbers that follows one rule at every spot: everything on the left side is smaller, and everything on the right side is bigger. This kind of tree is called a binary search tree, or BST.

You also get one number, the target. Find the spot in the tree that holds the target and give it back. If the target is not in the tree, give back null.

A story to remember it

Picture it

Examples

Way 1: the simple way

Forget the rule and check every spot, like knocking on every door in the forest. Use a waiting line: start with the top, and each time you check someone, add their children to the back of the line.

1. Put the top in the line.
2. Take the front of the line. If it holds the target, return it.
3. Otherwise add its left and right children to the line, and repeat.
4. If the line runs empty, return null.

import java.util.*;

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null) return null;
        Queue<TreeNode> line = new ArrayDeque<>();
        line.add(root);
        while (!line.isEmpty()) {
            TreeNode node = line.poll();
            if (node.val == val) return node;          // knocked on the right door
            if (node.left != null) line.add(node.left);
            if (node.right != null) line.add(node.right);
        }
        return null;                                   // knocked on every door, no luck
    }
}

How long it takes: in the worst case we check all n spots, O(n). Extra room: the line can hold a whole row of the tree, which is up to about n / 2, so O(n). It works on any tree, but it throws away the one thing that makes a BST special.

Way 2: the clever way

Use the signposts. Stand at the top with one finger, curr.

1. If curr is null, the path ended. Return null.
2. If curr holds the target, return it.
3. If the target is smaller, move curr to the left child. If bigger, move to the right child.
4. Repeat.

Each step throws away a whole side of the tree. The chips under the picture show the window the target must be in: it shrinks every step.

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        TreeNode curr = root;
        while (curr != null) {
            if (val == curr.val) return curr;           // found it
            curr = (val < curr.val) ? curr.left         // smaller: go left
                                    : curr.right;       // bigger: go right
        }
        return null;                                    // the path ended
    }
}

How long it takes: one look per row of the tree, so O(h), where h is the height. In a bushy, balanced tree h is about log n (a tree of a million numbers is only about 20 rows tall). In a stick shaped tree h is n. Extra room: one finger, O(1).

Another way: recursion

The same idea, written as "ask the correct child to search for you". It reads nicely but every waiting call sits on the call stack, so it uses O(h) extra room.

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null || root.val == val) return root;
        return val < root.val ? searchBST(root.left, val)
                              : searchBST(root.right, val);
    }
}

Watch out for

• An empty tree. The loop never runs and you return null, which is right.
• Duplicates. Most BST problems have none. If they are allowed, decide where equal values live (often the right side) and keep it the same for insert and search.
• Saying the time is O(log n) without the word "balanced". Interviewers listen for this. The honest answer is O(h).

What interviewers ask next

• Insert a value. Walk down the same way. When you fall off the tree, hang a new spot there. Still O(h).
• Find the value closest to the target. Walk the same path and remember the closest number you passed. The closest one is always on that path.
• Find the smallest value at least as big as the target (the ceiling). Walk down. Each time you go left, the spot you left is a candidate. The last candidate wins.
• How do you keep h small? Use a self balancing tree, like a red black tree or an AVL tree. Java's TreeMap is a red black tree, so get is O(log n) there.
• Why not keep a sorted array and use binary search? Search is the same speed, but inserting into an array shifts everything, O(n). A balanced BST inserts in O(log n).

Remember this

Grown-up words: the forest with signposts is a binary search tree, each fork is a node, the top is the root, the road you walk is the search path, the number of rows is the height h, and knocking on every door is a breadth first traversal.