Log inSign up
easyLeetCodeNot Started

Search in a Binary Search Tree

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

BST
Solve on LeetCode
Lesson

Problem Statement

You are given the root of a Binary Search Tree (BST) and an integer val.

Find the node in the BST whose value equals val and return the subtree rooted with that node. If such a node does not exist, return null.

Constraints:

  • The number of nodes in the tree is in the range [1, 5000].
  • 1 <= Node.val <= 107
  • root is a binary search tree.
  • 1 <= val <= 107

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Apply the core BST ordering invariant to search queries.
  • Contrast O(H) directed search with O(N) generic tree traversal.
  • Implement the O(1) space iterative while loop.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Search key in Binary Search Tree.
  • Return node/subtree reference.
  • Single path traversal.

Algorithmic Decision Tree:

  • val < curr.val: curr = curr.left.
  • val > curr.val: curr = curr.right.
  • val == curr.val: return curr.

Connected Patterns:

Insert into a Binary Search TreeDelete Node in a BSTBinary Search

1. Full Tree DFS (Unordered Search)

Intuition

Visit every node in the tree using recursion. Check if (root.val == val) return root. Otherwise search left and search right. Takes O(N) time and O(H) stack space.

When to apply: Baseline comparison for generic binary trees.

Algorithm

  1. Traverse every node in the tree using DFS and return the matching node without using BST ordering.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3struct TreeNode {
4 int val;
5 TreeNode* left;
6 TreeNode* right;
7 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
8};
9
10class Solution {
11public:
12 TreeNode* searchBST(TreeNode* root, int val) {
13 if (!root) return nullptr;
14 if (root->val == val) return root;
15 TreeNode* left = searchBST(root->left, val);
16 if (left) return left;
17 return searchBST(root->right, val);
18 }
19};
20
21int main() {
22 TreeNode* root = new TreeNode(4);
23 root->left = new TreeNode(2);
24 root->right = new TreeNode(7);
25 root->left->left = new TreeNode(1);
26 root->left->right = new TreeNode(3);
27
28 Solution sol;
29 TreeNode* res = sol.searchBST(root, 2);
30 std::cout << "Found: " << (res ? res->val : -1) << std::endl;
31 return 0;
32}

Time & Space Complexity

  • Time complexity: O(N)
  • Space complexity: O(H) recursion stack space

2. Recursive BST Search

Intuition

1. If !root || root.val == val return root. 2. If val < root.val return searchBST(root.left, val). 3. Return searchBST(root.right, val). Runs in O(H) time and O(H) stack space.

When to apply: Concise recursive solution.

Algorithm

  1. Recurse left if target < val, recurse right if target > val, return root on match.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3struct TreeNode {
4 int val;
5 TreeNode* left;
6 TreeNode* right;
7 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
8};
9
10class Solution {
11public:
12 TreeNode* searchBST(TreeNode* root, int val) {
13 if (!root || root->val == val) return root;
14 if (val < root->val) return searchBST(root->left, val);
15 return searchBST(root->right, val);
16 }
17};
18
19int main() {
20 TreeNode* root = new TreeNode(4);
21 root->left = new TreeNode(2);
22 root->right = new TreeNode(7);
23 root->left->left = new TreeNode(1);
24 root->left->right = new TreeNode(3);
25
26 Solution sol;
27 TreeNode* res = sol.searchBST(root, 2);
28 std::cout << "Found: " << (res ? res->val : -1) << std::endl;
29 return 0;
30}

Time & Space Complexity

  • Time complexity: O(H) where H is tree height
  • Space complexity: O(H) recursion stack space

3. Iterative BST Search (O(1) Auxiliary Space)

Intuition

1. Set curr = root. 2. While curr != null && curr.val != val: - If val < curr.val, move curr = curr.left. - Else move curr = curr.right. 3. Return curr. Achieves O(H) time and strictly O(1) auxiliary space.

When to apply: Optimal in both time and space. Industry standard.

Algorithm

  1. Traverse tree using a simple while-loop, updating curr based on comparisons with val.

Iterative BST Search Trace

2 of 2 questions left today
Step 1 / 2
Trace timeline50% explored
Current operationSTEP 1 OF 2
In a BST, values < 4 are strictly in the left subtree
Visual state
Values and pointers at this exact step
tree
This tree trace has no visual items for the current step yet. Add step.items (and connections where needed) to render its structure accurately.
Check / comparison
curr = 4. val (2) < 4 -> curr moves to 4.left (2).
Decision / next transition
1
Why this step matters

In a BST, values < 4 are strictly in the left subtree.

Step 1 / 2
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3struct TreeNode {
4 int val;
5 TreeNode* left;
6 TreeNode* right;
7 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
8};
9
10class Solution {
11public:
12 TreeNode* searchBST(TreeNode* root, int val) {
13 TreeNode* curr = root;
14 while (curr && curr->val != val) {
15 if (val < curr->val) curr = curr->left;
16 else curr = curr->right;
17 }
18 return curr;
19 }
20};
21
22int main() {
23 TreeNode* root = new TreeNode(4);
24 root->left = new TreeNode(2);
25 root->right = new TreeNode(7);
26 root->left->left = new TreeNode(1);
27 root->left->right = new TreeNode(3);
28
29 Solution sol;
30 TreeNode* res = sol.searchBST(root, 2);
31 std::cout << "Found: " << (res ? res->val : -1) << std::endl;
32 return 0;
33}

Time & Space Complexity

  • Time complexity: O(H) where H is tree height
  • Space complexity: O(1) auxiliary space

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Full Tree DFS (Unordered Search)O(N)O(H) recursion stack spaceTraverse every node in the tree using DFS and return the matching node without using BST ordering.O(N)
2.Recursive BST SearchO(H) where H is tree heightO(H) recursion stack spaceRecurse left if target < val, recurse right if target > val, return root on match.O(H) where H is tree height
3.Iterative BST Search (O(1) Auxiliary Space)OptimalO(H) where H is tree heightO(1) auxiliary spaceTraverse tree using a simple while-loop, updating curr based on comparisons with val.O(H) where H is tree height

Common Pitfalls & Crucial Edge Cases

Reversing comparison directions

Going left when val > curr.val.

Null pointer dereference

Forgetting while (curr) before accessing curr.val.

Searching both subtrees

Falling back to generic binary tree traversal.

Crucial Edge Cases to Validate:

  • Value is the root node — Returns root in O(1) time.
  • Value does not exist in the BST — Returns null.
  • Empty tree (`root == null`) — Returns null.
  • Value is a leaf node — Successfully navigates down to the leaf and returns it.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Write the concise 4-line iterative while-loop.
  2. State the complexity clearly: 'Average O(log N) time on balanced tree, worst-case O(N) on skewed tree, strictly O(1) auxiliary space.'
  3. Point out that the return value represents the entire subtree rooted at that node.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the average time complexity of searching in a balanced BST with N nodes?

2.What is the worst-case time complexity of searching in an unbalanced (skewed) BST?

3.Why is the iterative implementation preferred over the recursive implementation for searching a BST?

Back to DSA Sheet