#700 Search in a Binary Search Tree

Easysolve on LeetCode ↗

frequently reported atGoogle Meta Amazon Microsoft Bloomberg

the problem

In plain words

Return the node whose value equals val (the subtree rooted there), or null if no such node exists.

in root = [4,2,7,1,3], val = 2

out [2,1,3]

in root = [4,2,7,1,3], val = 5

out []

1 ≤ number of nodes ≤ 5000
1 ≤ Node.val ≤ 10⁷
root is a BST
1 ≤ val ≤ 10⁷

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternBST property

Each comparison tells you which side the value must be on. Never look at the other side.

solutions

From brute force to optimal

Ignore the ordering and DFS everywhere, like a plain binary tree.

If root is null or matches, return it.
Search left; if not found, search right.

timeO(n)

May visit every node.

spaceO(h)

Recursion stack.

javajava.util.*

1class Solution {2    /** Ignores the BST order and searches everywhere, like in a plain binary tree. */3    public TreeNode searchBST(TreeNode root, int val) {4        if (root == null || root.val == val) return root;5        TreeNode left = searchBST(root.left, val);6        return left != null ? left : searchBST(root.right, val);7    }8}

Recurse into only one side, chosen by comparing.

null or match → return root.
val < root.val → search left, else search right.

timeO(h)

One node per level.

spaceO(h)

One stack frame per level (tail calls aren't optimized in Java).

javajava.util.*

1class Solution {2    public TreeNode searchBST(TreeNode root, int val) {3        if (root == null || root.val == val) return root;4        return val < root.val5                ? searchBST(root.left, val)    // everything smaller lives on the left6                : searchBST(root.right, val);  // everything larger lives on the right7    }8}

Same walk with a single pointer.

cur = root.
While cur != null: match → return; smaller → left; larger → right.
Return null.

timeO(h)

One node per level: O(log n) balanced, O(n) skewed.

spaceO(1)

Just the pointer.

javajava.util.*

1class Solution {2    public TreeNode searchBST(TreeNode root, int val) {3        TreeNode cur = root;4        while (cur != null) {5            if (val == cur.val) return cur;6            if (val < cur.val) cur = cur.left;     // smaller → left7            else cur = cur.right;                  // larger → right8        }9        return null;                               // fell off the tree: not here10    }11}

sim

Dry run

loading simulation…

javajava.util.*

1class Solution {2    public TreeNode searchBST(TreeNode root, int val) {3        TreeNode cur = root;4        while (cur != null) {5            if (val == cur.val) return cur;6            if (val < cur.val) cur = cur.left;     // smaller → left7            else cur = cur.right;                  // larger → right8        }9        return null;                               // fell off the tree: not here10    }11}

in the room

How to say it in the interview

talk track

Mention you're returning the node (a subtree), not a boolean.
State O(h) and both cases of h.

traps

Searching both subtrees like a plain binary tree — O(n) instead of O(h).
In the recursive version, calling searchBST(root.left, val) without return — the found node is lost.

what they ask next

Follow-ups

Closest Binary Search Tree Value (LC 270)?

Same walk; keep the value with the smallest |node.val − target| seen on the path.

before you submit

Edge cases to test

val is at the root → return the root itself (the whole tree).
val is missing → the walk falls off the tree and returns null.
A skewed tree of 5000 nodes → up to 5000 steps; the iterative walk needs no stack at all.

practise next