LeetCode 700 - Search in a Binary Search Tree

Difficulty: 🟢 Easy
Topics: Tree, Binary Search Tree, Binary Tree

Solution

Problem Understanding

This problem gives us the root node of a Binary Search Tree, commonly abbreviated as a BST, along with an integer value val. Our goal is to locate the node whose value is exactly equal to val and return that node. Since the problem asks us to return the subtree rooted at that node, returning the node itself is sufficient because every node already contains references to its children.

A Binary Search Tree has a very important property:

Every value in the left subtree is smaller than the current node's value
Every value in the right subtree is larger than the current node's value

This ordering property is what allows us to search efficiently.

The input is a tree structure represented by root, and an integer val representing the target we want to find. The expected output is either:

The node whose value equals val
null or None if no such node exists

For example, if the tree is:

and val = 2, we return the node containing 2. That returned node represents this subtree:

      2
     / \
    1   3

The constraints tell us that the tree contains between 1 and 5000 nodes. This is small enough that even a full traversal would work within time limits, but the BST property allows us to do better than scanning every node.

The problem guarantees that the input tree is a valid Binary Search Tree. This guarantee is extremely important because our optimized solution relies entirely on BST ordering rules.

There are several edge cases worth considering:

The target value may not exist anywhere in the tree
The root itself may contain the target value
The target may be located deep in the tree
The tree could be heavily skewed, behaving almost like a linked list
The tree contains at least one node, so root is not guaranteed to be None, but handling None safely is still good defensive practice

Approaches

Brute Force Approach

The simplest possible solution is to ignore the BST property entirely and perform a complete traversal of the tree. We could use either Depth First Search or Breadth First Search.

The algorithm would visit every node one by one and compare its value with val. If a match is found, we return that node immediately. If we finish traversing the entire tree without finding the value, we return None.

This approach is correct because it eventually checks every node in the tree, so if the value exists, we are guaranteed to find it.

However, this solution wastes the BST structure. Even if the current node's value tells us exactly which direction we should search, the brute force method still explores both subtrees.

Optimal Approach

The key insight is that the tree is a Binary Search Tree.

At every node:

If val equals the current node's value, we found the answer
If val is smaller, the target can only exist in the left subtree
If val is larger, the target can only exist in the right subtree

This means we never need to search both sides of the tree. At each step, we eliminate half of the remaining search space, similar to binary search on a sorted array.

Because of this property, we can traverse only one path from the root downward until we either find the target or reach a None node.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(h)	Traverses the entire tree regardless of BST ordering
Optimal	O(h)	O(1) iterative, O(h) recursive	Uses BST property to search only one branch

Here:

n is the number of nodes
h is the height of the tree

In a balanced BST, h = log n. In a skewed BST, h = n.

Algorithm Walkthrough

Optimal Iterative BST Search

Start at the root node of the tree.

The root is the entry point into the BST. Every decision about where to move next depends on comparing the target value against the current node. 2. Compare the current node's value with val.

There are three possible cases:

If they are equal, we found the target node and return it immediately.
If val is smaller, the BST property guarantees the target can only exist in the left subtree.
If val is larger, the BST property guarantees the target can only exist in the right subtree.

Move to the appropriate child node.

Depending on the comparison:

Move to current.left if val < current.val
Move to current.right if val > current.val

This eliminates half of the remaining search space at every step. 4. Continue until either:

The target node is found
The current node becomes None

If the current node becomes None, it means we reached a dead end where the target value does not exist in the tree. 5. Return None if the value was not found.

Why it works

The correctness comes directly from the BST invariant:

Every left subtree contains only smaller values
Every right subtree contains only larger values

At each step, the algorithm discards one entire subtree that cannot possibly contain the target. Since we only move into the subtree where the target could legally exist, we never miss the correct node. Eventually, we either find the node or determine that no valid path remains.

Python Solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import Optional

class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        current = root
        
        while current:
            if current.val == val:
                return current
            
            if val < current.val:
                current = current.left
            else:
                current = current.right
        
        return None

The implementation begins by storing the root node in a variable called current. This variable tracks our current position during traversal.

The while current: loop continues as long as we still have a valid node to examine. If current becomes None, we know the search path ended without finding the target.

Inside the loop, the first condition checks whether the current node already contains the target value. If it does, we immediately return the node.

If the target is smaller than the current node's value, we move left because the BST property guarantees all smaller values live in the left subtree.

Otherwise, we move right because the target must be larger.

If the loop finishes without returning a node, the value does not exist in the BST, so we return None.

This implementation is iterative, which avoids recursive call stack overhead and keeps auxiliary space usage minimal.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func searchBST(root *TreeNode, val int) *TreeNode {
    current := root

    for current != nil {
        if current.Val == val {
            return current
        }

        if val < current.Val {
            current = current.Left
        } else {
            current = current.Right
        }
    }

    return nil
}

The Go implementation follows the exact same logic as the Python version. The main language-specific difference is that Go uses nil instead of None.

Pointers are used directly for tree nodes, so returning a subtree simply means returning the pointer to the matching node.

Go does not require explicit type hints because the compiler infers types from declarations like current := root.

Since node values are constrained to at most 10^7, integer overflow is not a concern with Go's standard integer type.

Worked Examples

Example 1

Input:

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

Tree:

Step-by-step traversal:

Step	Current Node	Comparison	Action
1	4	2 < 4	Move left
2	2	2 == 2	Return node

Returned subtree:

      2
     / \
    1   3

Example 2

Input:

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

Tree:

Step-by-step traversal:

Step	Current Node	Comparison	Action
1	4	5 > 4	Move right
2	7	5 < 7	Move left
3	None	Target not found	Return None

Since the traversal reaches None, the value does not exist in the tree.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(h)	We traverse at most one path from root to leaf
Space	O(1)	The iterative solution uses constant extra memory

The time complexity depends on the height of the tree because the algorithm only follows one branch at each step.

In a balanced BST, the height is logarithmic, so the runtime becomes:

O(log n)

In the worst case, when the tree is completely skewed, the height becomes:

O(n)

The iterative implementation only stores a few variables regardless of tree size, so the auxiliary space complexity is constant.

Test Cases

# Definition for testing
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, val):
        current = root

        while current:
            if current.val == val:
                return current

            if val < current.val:
                current = current.left
            else:
                current = current.right

        return None

# Build sample BST
#
#         4
#        / \
#       2   7
#      / \
#     1   3
#
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(7)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)

sol = Solution()

# Example 1: target exists
result = sol.searchBST(root, 2)
assert result is not None and result.val == 2  # Found existing node

# Example 2: target does not exist
result = sol.searchBST(root, 5)
assert result is None  # Missing value returns None

# Root node is target
result = sol.searchBST(root, 4)
assert result is root  # Root should be returned directly

# Leaf node search
result = sol.searchBST(root, 1)
assert result is not None and result.val == 1  # Left leaf node

# Right subtree search
result = sol.searchBST(root, 7)
assert result is not None and result.val == 7  # Right child

# Single-node tree, value exists
single = TreeNode(10)
result = sol.searchBST(single, 10)
assert result is single  # Single-node success

# Single-node tree, value missing
result = sol.searchBST(single, 5)
assert result is None  # Single-node failure

# Skewed tree test
#
# 1
#  \
#   2
#    \
#     3
#
skewed = TreeNode(1)
skewed.right = TreeNode(2)
skewed.right.right = TreeNode(3)

result = sol.searchBST(skewed, 3)
assert result is not None and result.val == 3  # Deep right traversal

# Search smaller than all nodes
result = sol.searchBST(root, 0)
assert result is None  # Value smaller than minimum

# Search larger than all nodes
result = sol.searchBST(root, 100)
assert result is None  # Value larger than maximum

Test	Why
Search for `2`	Validates successful search in left subtree
Search for `5`	Validates missing value handling
Search for root value	Ensures immediate return works
Search for leaf node	Confirms traversal reaches leaves correctly
Search in right subtree	Validates right traversal logic
Single-node success	Smallest valid BST
Single-node failure	Ensures missing values work in minimal tree
Skewed tree	Tests worst-case height behavior
Value smaller than minimum	Ensures left boundary handling
Value larger than maximum	Ensures right boundary handling

Edge Cases

One important edge case is when the target value is stored in the root itself. A buggy implementation might unnecessarily continue traversing instead of returning immediately. In this solution, the equality check happens before any movement, so the root is returned instantly when it matches.

Another critical edge case is when the target value does not exist in the tree. Some incorrect implementations accidentally dereference a None or nil node while continuing traversal. This implementation safely terminates the loop as soon as the current node becomes None, then returns None.

A skewed BST is another important scenario. A tree shaped like a linked list can expose recursion depth problems in recursive solutions. Since this implementation is iterative, it handles deeply skewed trees safely without risking stack overflow.

A final edge case occurs when the tree contains only one node. The algorithm must correctly handle both outcomes: either the single node matches the target or it does not. Because the loop checks equality before traversal, both cases are handled naturally without special-case logic.