Introduction

Binary Search Tree (BST) is one of the most important data structures frequently asked in coding interviews and competitive programming. LeetCode 700 - Search in a Binary Search Tree is a beginner-friendly problem that helps developers understand how BST properties can be utilized to perform efficient searches.

In this article, we will discuss the problem statement, understand the BST property, develop an intuition, analyze the recursive solution, perform a dry run, and evaluate the time and space complexity.

Problem Statement

Given the root of a Binary Search Tree (BST) and an integer value val, find the node whose value equals val and return the subtree rooted at that node.

If the value does not exist in the BST, return null.

Problem Link

LeetCode 700 - Search in a Binary Search Tree

Example 1

Input:

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

val = 2

Output:

[2,1,3]

Explanation:

The node with value 2 exists in the BST. Therefore, we return the subtree rooted at node 2.

Example 2

Input:

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

val = 5

Output:

[]

Explanation:

Value 5 does not exist in the BST, so we return null.

Understanding the Binary Search Tree Property

A Binary Search Tree follows these rules:

1. All values in the left subtree are smaller than the root node.
2. All values in the right subtree are greater than the root node.
3. Both left and right subtrees are also BSTs.

Example:

Suppose we need to search for value 3:

1. Start at 4.
2. Since 3 < 4, move left.
3. Reach node 2.
4. Since 3 > 2, move right.
5. Reach node 3.
6. Value found.

Instead of traversing every node, BST allows us to eliminate half of the search space at each step.

Intuition

The BST property gives us a clear direction while searching:

1. If the current node's value equals val, return the node.
2. If val is smaller than the current node's value, search in the left subtree.
3. If val is greater than the current node's value, search in the right subtree.
4. If we reach a null node, the value does not exist.

This naturally leads to a recursive solution.

Approach

Algorithm

1. If the current node is null, return null.
2. If the current node value equals val, return the node.
3. If val is smaller than the current node value, recursively search the left subtree.
4. Otherwise, recursively search the right subtree.
5. Return the result obtained from recursion.

Java Solution

Code Explanation

Helper Function: solve()

This function recursively searches for the target value.

If the node is null, the value is not present.

If the value matches, return the current node.

When the target value is smaller, move to the left subtree.

When the target value is larger, move to the right subtree.

Main Function: searchBST()

Handles the empty tree case.

If the root itself contains the target value, return immediately.

Otherwise, begin recursive searching.

Dry Run

Input:

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

val = 2

Tree:

Step 1

Current Node = 4

4 > 2

Move to left subtree.

Step 2

Current Node = 2

2 == 2

Target found.

Return subtree:

Output:

[2,1,3]

Another Dry Run

Input:

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

val = 5

Step 1

Current Node = 4

5 > 4

Move right.

Step 2

Current Node = 7

5 < 7

Move left.

Step 3

Current Node = null

Value not found.

Return null.

Complexity Analysis

Time Complexity

Best Case:

O(1)

When the root itself contains the target value.

Average Case:

O(log n)

For a balanced BST, each comparison reduces the search space by half.

Worst Case:

O(n)

When the BST becomes skewed like a linked list.

Space Complexity

O(h)

Where h is the height of the tree due to recursive function calls.

Balanced BST:

O(log n)

Skewed BST:

O(n)

Why This Solution Works

The solution efficiently utilizes the Binary Search Tree property instead of performing a full tree traversal.

At every node:

1. Left subtree is searched only when necessary.
2. Right subtree is searched only when necessary.
3. Unnecessary branches are ignored.

This significantly improves performance compared to a normal binary tree search.

Interview Tips

When solving BST search problems in interviews:

1. Always mention the BST property first.
2. Explain why only one subtree needs to be explored.
3. Discuss both balanced and skewed tree scenarios.
4. Mention iterative optimization if asked about reducing recursion stack space.

Conclusion

LeetCode 700 - Search in a Binary Search Tree is a fundamental BST problem that demonstrates how the ordered structure of a BST enables efficient searching. By leveraging BST properties, we can quickly locate a target node without traversing the entire tree.

The recursive approach is simple, clean, and highly intuitive, making it an excellent solution for coding interviews and DSA practice. Understanding this problem builds a strong foundation for more advanced BST operations such as insertion, deletion, validation, and range queries.