What is the brute force approach and complexity for Search in a Binary Search Tree?

Ignore the BST order: check a node, then search its left and right subtrees with time complexity O(N) and space complexity O(H).

What is the optimal approach and complexity for Search in a Binary Search Tree?

Compare `val` with the current node, then step to the one child that can hold it with optimal time complexity O(H) and space complexity O(1).

How do you identify the pattern for Search in a Binary Search Tree?

Look for key signals in the prompt: "binary search tree" indicates Left < node < right. One comparison tells you which side can hold the target.; "return the node with value val" indicates Return the node itself, not a copy. Its subtree comes with it.; "not found → null" indicates The walk must stop cleanly when it falls off the tree..

Search in a Binary Search Tree

Easy·LeetCode #700Basic Anchor

LeetCode

Jump:

30-Second Mental ModelTree DFS — BST properties (walk one path, go left or right)

Complexity:O(N)→O(H)

Key Insight

Start at the root. If val is smaller than the current value, the answer can only be on the left, so the right side is thrown away. If it is bigger, go right. Stop when the value matches or the walk runs off the tree.

Core Validity Invariant

The answer, if it exists, is always inside the subtree rooted at cur.

Problem

You are given the root of a binary search tree and a number val.

Find the node whose value is val, and return that node. The node keeps its children, so its whole subtree comes back with it. If no node holds val, return null.

Input

The root of a binary search tree (between 1 and 5000 nodes) and an integer val.

Output

The node whose value is val (the subtree rooted at it), or null if no node has that value.

Example 1

Input: root = [4, 2, 7, 1, 3], val = 2

Output: the node 2, with children 1 and 3 (LeetCode shows [2, 1, 3])

Node 2 holds the value we want, so we return it. Its subtree is 2 with children 1 and 3.

Example 2

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

Output: null

No node holds 5. The walk goes 4 → 7, then 7 has no left child, so it runs off the tree.

Constraints

• The number of nodes is between 1 and 5000
• 1 ≤ Node.val ≤ 10^7
• root is a binary search tree
• 1 ≤ val ≤ 10^7

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
The tree is a binary search tree. If I stand at one node and compare val with its value, what does that tell me about the two sides?
2.
Could val sit in the right subtree of a node whose value is bigger than val? Why or why not?
3.
Which two things can end my search, and what does each one mean for the answer?
4.
Do I need recursion or a stack here, or is a single pointer enough?
5.
On a chain of 5000 nodes that leans to the right, how many nodes can the search visit? What changes for a balanced tree?

Brute force approach

Idea

Treat the tree like any binary tree. Check the current node. If it is not the one, search the left subtree, then the right. The BST order is never used, so the search can visit every node in the tree.

Thinking process

1
The tree is still a tree, so I can search it the way I would search any tree: check the node, then search its children.
2
On [4,2,7,1,3] looking for 3: check 4 (no), search left: check 2 (no), search its left: 1 (no), then its right: 3 (yes). Four nodes visited.
3
Looking for 5 on the same tree: no branch finds it, so all five nodes are visited before the search gives up.
4
This works, but a BST already tells me that one side of each node cannot hold the value. Ignoring that fact means the cost is the whole tree.

Visual

Blue: the node being visited. Green: visited already. The search goes left first, then right, and never uses the BST order. A missing value makes it visit all 8 nodes.

Brute force visits everythingroot = [5, 3, 8, 2, 4, 7, 9, 1], val = 6step 1/9

State

target: 6
visited: 1
of total: 8

5 ≠ 6 → keep searching

Visit 5: it is not 6. Search its left side, then its right side.

Code & Implementation

brute.cpp

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        // Ignores the BST order: check this node, then search both sides.
        if (!root) return nullptr;
        if (root->val == val) return root;
        TreeNode* found = searchBST(root->left, val);
        if (found) return found;
        return searchBST(root->right, val);
    }
};

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        // Ignores the BST order: check this node, then search both sides.
        if (root == null) return null;
        if (root.val == val) return root;
        TreeNode found = searchBST(root.left, val);
        if (found != null) return found;
        return searchBST(root.right, val);
    }
}

from typing import Optional

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

class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        # Ignores the BST order: check this node, then search both sides.
        if not root:
            return None
        if root.val == val:
            return root
        found = self.searchBST(root.left, val)
        if found:
            return found
        return self.searchBST(root.right, val)

export class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = (val === undefined ? 0 : val);
        this.left = (left === undefined ? null : left);
        this.right = (right === undefined ? null : right);
    }
}

export function searchBST(root: TreeNode | null, val: number): TreeNode | null {
    // Ignores the BST order: check this node, then search both sides.
    if (!root) return null;
    if (root.val == val) return root;
    const found = searchBST(root.left, val);
    if (found) return found;
    return searchBST(root.right, val);
}

Complexity

Time O(N)Space O(H)

A missing value, or a value deep on the right, makes this visit every node, so the worst case is N. H is the recursion depth. The optimal visits one node per level, so it costs O(H) time and uses O(1) space.

Optimized approach

Idea

Start from brute force

Brute force searches both sides of every node, as if the tree had no order.

Find the repeated work

On a miss, it visits every node. But in a BST one comparison says which side can hold val, so the other side is never needed.

Define the state — what variables do I need?

cur: The node we are looking at now. If `val` is in the tree, it is inside cur's subtree.
val: The value we are searching for. It never changes.

Define validity

The answer, if it exists, is always inside the subtree rooted at cur.

Define the transitions — when does each pointer move, and why is it safe?

`val` is smaller than cur->val

cur = cur->left

Everything in the right subtree is bigger than cur, so it is bigger than val too and cannot match.

`val` is bigger than cur->val

cur = cur->right

Everything in the left subtree is smaller than cur, so it is smaller than val too and cannot match.

cur->val == val, or cur is null

stop and return cur

A match is the answer. Null means the walk fell off the tree, so the value is not in it.

What does the current window add to the answer?

The walk keeps no running answer. The answer is the node where the walk stops, or null.

Code & Implementation

optimal.cpp

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        // One comparison per level: the BST order says which side can hold val.
        TreeNode* cur = root;
        while (cur && cur->val != val) {
            cur = val < cur->val ? cur->left : cur->right;
        }
        return cur;  // the matching node, or nullptr if the walk fell off the tree
    }
};

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        // One comparison per level: the BST order says which side can hold val.
        TreeNode cur = root;
        while (cur != null && cur.val != val) {
            cur = val < cur.val ? cur.left : cur.right;
        }
        return cur;  // the matching node, or null if the walk fell off the tree
    }
}

from typing import Optional

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

class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        # One comparison per level: the BST order says which side can hold val.
        cur = root
        while cur and cur.val != val:
            cur = cur.left if val < cur.val else cur.right
        return cur  # the matching node, or None if the walk fell off the tree

export class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = (val === undefined ? 0 : val);
        this.left = (left === undefined ? null : left);
        this.right = (right === undefined ? null : right);
    }
}

export function searchBST(root: TreeNode | null, val: number): TreeNode | null {
    // One comparison per level: the BST order says which side can hold val.
    let cur = root;
    while (cur && cur.val !== val) {
        cur = val < cur.val ? cur.left : cur.right;
    }
    return cur;  // the matching node, or null if the walk fell off the tree
}

Complexity

Time O(H)Space O(1)

H is the height. A balanced tree with 5000 nodes has a height of about 13, so the walk takes about 13 steps. A chain that leans one way has H = N, so the worst case is still O(N), but a balanced tree is fast.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Ignore the BST order: check a node, then search its left and right subtrees	O(N)	O(H)
Optimal	Compare `val` with the current node, then step to the one child that can hold it	O(H)	O(1)

Why does this belong to this pattern?

Clues in the problem statement

“binary search tree”Left < node < right. One comparison tells you which side can hold the target.
“return the node with value val”Return the node itself, not a copy. Its subtree comes with it.
“not found → null”The walk must stop cleanly when it falls off the tree.

BST order: left < node < right+one comparison per level+return the node or null→Tree DFS — BST properties (walk one path, go left or right)

This is binary search on a tree. Each comparison throws away one whole side, the same way binary search throws away half of a sorted array. The tree version needs no stack or recursion, because each step keeps only one candidate: the current node. The search does not need the other side because the BST order already rules it out.

Don't make this mistake

Searching both sides like a plain tree (pattern confusion)

✗ TreeNode* found = searchBST(root->left, val); if (found) return found; return searchBST(root->right, val);

✓ if (!root || root->val == val) return root; return searchBST(val < root->val ? root->left : root->right, val);

The two-sided search still returns the right node, so a small test passes. But it throws away the BST order. On [5,3,8,2,4,7,9,1] with val = 6, the two-sided search visits all 8 nodes. The BST walk goes 5 → 8 → 7 and stops after 3.

Comparing with the wrong side

✗ cur = val > cur->val ? cur->left : cur->right;

✓ cur = val < cur->val ? cur->left : cur->right;

The two sides are swapped, so the walk goes the wrong way. On [5,3,8,2,4,7,9,1] with val = 4: 4 < 5, but the code goes right to 8, then left to 7, then null. It returns null even though 4 is in the tree.

Returning a new node instead of the one in the tree

✗ return new TreeNode(cur->val);

✓ return cur;

The value is right, but a new node has no children, so the subtree is lost. The answer is the existing node. On [4,2,7,1,3] with val = 2, the copy would lose the children 1 and 3.

Dereferencing null when the value is missing

✗ while (cur->val != val) { cur = val < cur->val ? cur->left : cur->right; }

✓ while (cur && cur->val != val) { cur = val < cur->val ? cur->left : cur->right; }

When val is not in the tree, cur becomes null and cur->val crashes. On [4,2,7,1,3] with val = 5, the walk goes 4 → 7 → null, and the check on null is the crash.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Tree DFS translate into production architectures and low-level memory mechanics.

LLD Architecture