Search in a Binary Search Tree

Problem

Given the root of a BST and a value, return the subtree rooted at the node with that value, or null if not found.

Constraints

• 1 ≤ nodes ≤ 5000
• 1 ≤ Node.val ≤ 10⁷

Approach — Tree Traversal

This is a Tree Traversal problem. The idea: traverse the tree — DFS recursively, or BFS level by level — and combine the results from each subtree. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n) time.

Solution code

Python

class Solution:
    def searchBST(self, root, val):
        while root and root.val != val:
            root = root.left if val < root.val else root.right
        return root

Java

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

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.