Search in a BST

🎯

Search in a BST

easyTREEAmazonGoogle

Imagine you have a large directory of sorted contacts stored as a binary search tree, and you want to quickly find if a particular contact exists.

💡 This problem is about searching a value in a Binary Search Tree (BST). Beginners often struggle because they confuse BST search with normal binary tree traversal or linear search, missing the BST property that allows efficient searching.

📋

Problem Statement

Given the root node of a Binary Search Tree (BST) and a value val, determine if the BST contains a node with the value val. Return the subtree rooted with that node if it exists, otherwise return null.

The number of nodes in the tree is in the range [1, 10^5]Node values are unique integers-10^9 ≤ Node.val, val ≤ 10^9

💡

Example

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

Output[2,1,3]

The node with value 2 is found, and its subtree includes nodes 1 and 3.

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

Outputnull

No node with value 5 exists in the BST.

• Searching for the root node value → should return entire tree
• Searching for a leaf node value → should return that leaf node
• Searching for a value smaller than all nodes → should return null
• Searching for a value larger than all nodes → should return null

⚠️

Common Mistakes

Ignoring BST property and searching both subtrees

Code runs slower, time complexity degrades to O(n)

✅ Use BST property to decide which subtree to search

Not handling null nodes properly

Runtime errors or infinite recursion

✅ Always check if current node is null before accessing its value

Using recursion without considering stack overflow for deep trees

Stack overflow error on large or skewed trees

✅ Use iterative approach for large inputs or mention recursion depth limits

Returning wrong node or subtree

Incorrect output, partial subtree or wrong node returned

✅ Return the node where value matches exactly, not just a partial match

🧠

Brute Force (Recursive Full Tree Traversal)

💡 This approach exists to build intuition by ignoring BST properties and searching every node, helping beginners understand the problem structure before optimization.

Intuition

Traverse the entire tree recursively and check each node's value against the target. Return the node if found, else continue searching both left and right subtrees.

Algorithm

1. Start at the root node.
2. If the current node is null, return null (not found).
3. If the current node's value equals the target, return the current node.
4. Recursively search the left subtree; if found, return the result.
5. Otherwise, recursively search the right subtree and return the result.

💡 This approach is straightforward but inefficient because it does not use the BST property to skip subtrees.

</>

Code

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

def searchBST(root, val):
    if root is None:
        return None
    if root.val == val:
        return root
    left_search = searchBST(root.left, val)
    if left_search is not None:
        return left_search
    return searchBST(root.right, val)

# Example usage:
# Construct BST: 4
#               /   \
#              2     7
#             / \
#            1   3
root = TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode(7))
result = searchBST(root, 2)
print(result.val if result else 'null')

Line Notes

if root is None:Base case: if node is null, target not found here

if root.val == val:Check if current node matches target

left_search = searchBST(root.left, val)Search left subtree recursively

if left_search is not None:If found in left subtree, return immediately

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

public class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null) return null;
        if (root.val == val) return root;
        TreeNode leftSearch = searchBST(root.left, val);
        if (leftSearch != null) return leftSearch;
        return searchBST(root.right, val);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(4);
        root.left = new TreeNode(2);
        root.right = new TreeNode(7);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(3);
        Solution sol = new Solution();
        TreeNode res = sol.searchBST(root, 2);
        System.out.println(res != null ? res.val : "null");
    }
}

Line Notes

if (root == null) return null;Base case: no node means target not found

if (root.val == val) return root;Check current node for target

TreeNode leftSearch = searchBST(root.left, val);Search left subtree recursively

if (leftSearch != null) return leftSearch;Return immediately if found in left subtree

#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if (!root) return nullptr;
        if (root->val == val) return root;
        TreeNode* leftSearch = searchBST(root->left, val);
        if (leftSearch) return leftSearch;
        return searchBST(root->right, val);
    }
};

int main() {
    TreeNode* root = new TreeNode(4);
    root->left = new TreeNode(2);
    root->right = new TreeNode(7);
    root->left->left = new TreeNode(1);
    root->left->right = new TreeNode(3);
    Solution sol;
    TreeNode* res = sol.searchBST(root, 2);
    cout << (res ? to_string(res->val) : "null") << endl;
    return 0;
}

Line Notes

if (!root) return nullptr;Base case: no node means target not found

if (root->val == val) return root;Check current node for target

TreeNode* leftSearch = searchBST(root->left, val);Search left subtree recursively

if (leftSearch) return leftSearch;Return immediately if found in left subtree

class TreeNode {
    constructor(val=0, left=null, right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function searchBST(root, val) {
    if (root === null) return null;
    if (root.val === val) return root;
    const leftSearch = searchBST(root.left, val);
    if (leftSearch !== null) return leftSearch;
    return searchBST(root.right, val);
}

// Example usage:
const root = new TreeNode(4, new TreeNode(2, new TreeNode(1), new TreeNode(3)), new TreeNode(7));
const result = searchBST(root, 2);
console.log(result ? result.val : 'null');

Line Notes

if (root === null) return null;Base case: no node means target not found

if (root.val === val) return root;Check current node for target

const leftSearch = searchBST(root.left, val);Search left subtree recursively

if (leftSearch !== null) return leftSearch;Return immediately if found in left subtree

⏱

Complexity

TimeO(n)

SpaceO(h)

In worst case, we visit every node (n nodes). The recursion stack can go as deep as the tree height h.

💡 For n=20 nodes, this means up to 20 checks and recursion depth up to 20 in worst case.

Interview Verdict: Accepted but inefficient

This approach works but ignores BST properties, so it is slower than necessary.

🧠

Better (Recursive BST Property Search)

💡 This approach uses the BST property to skip unnecessary subtrees, improving efficiency and teaching how to leverage problem constraints.

Intuition

At each node, compare the target value with the node's value. If equal, return node. If target is smaller, search left subtree only; if larger, search right subtree only.

Algorithm

1. Start at the root node.
2. If the current node is null, return null.
3. If the current node's value equals the target, return the current node.
4. If target < current node's value, recursively search the left subtree.
5. Else, recursively search the right subtree.

💡 This approach is more efficient because it prunes half the tree at each step.

</>

Code

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

def searchBST(root, val):
    if root is None:
        return None
    if root.val == val:
        return root
    elif val < root.val:
        return searchBST(root.left, val)
    else:
        return searchBST(root.right, val)

# Example usage:
root = TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode(7))
result = searchBST(root, 2)
print(result.val if result else 'null')

Line Notes

if root is None:Base case: no node means target not found

if root.val == val:Check if current node matches target

elif val < root.val:If target smaller, search left subtree only

else:If target larger, search right subtree only

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

public class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null) return null;
        if (root.val == val) return root;
        else if (val < root.val) return searchBST(root.left, val);
        else return searchBST(root.right, val);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(4);
        root.left = new TreeNode(2);
        root.right = new TreeNode(7);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(3);
        Solution sol = new Solution();
        TreeNode res = sol.searchBST(root, 2);
        System.out.println(res != null ? res.val : "null");
    }
}

Line Notes

if (root == null) return null;Base case: no node means target not found

if (root.val == val) return root;Check current node for target

else if (val < root.val) return searchBST(root.left, val);Search left subtree if target smaller

else return searchBST(root.right, val);Search right subtree if target larger

#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if (!root) return nullptr;
        if (root->val == val) return root;
        else if (val < root->val) return searchBST(root->left, val);
        else return searchBST(root->right, val);
    }
};

int main() {
    TreeNode* root = new TreeNode(4);
    root->left = new TreeNode(2);
    root->right = new TreeNode(7);
    root->left->left = new TreeNode(1);
    root->left->right = new TreeNode(3);
    Solution sol;
    TreeNode* res = sol.searchBST(root, 2);
    cout << (res ? to_string(res->val) : "null") << endl;
    return 0;
}

Line Notes

if (!root) return nullptr;Base case: no node means target not found

if (root->val == val) return root;Check current node for target

else if (val < root->val) return searchBST(root->left, val);Search left subtree if target smaller

else return searchBST(root->right, val);Search right subtree if target larger

class TreeNode {
    constructor(val=0, left=null, right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function searchBST(root, val) {
    if (root === null) return null;
    if (root.val === val) return root;
    else if (val < root.val) return searchBST(root.left, val);
    else return searchBST(root.right, val);
}

const root = new TreeNode(4, new TreeNode(2, new TreeNode(1), new TreeNode(3)), new TreeNode(7));
const result = searchBST(root, 2);
console.log(result ? result.val : 'null');

Line Notes

if (root === null) return null;Base case: no node means target not found

if (root.val === val) return root;Check current node for target

else if (val < root.val) return searchBST(root.left, val);Search left subtree if target smaller

else return searchBST(root.right, val);Search right subtree if target larger

⏱

Complexity

TimeO(h)

SpaceO(h)

Each recursive call moves down one level of the tree, so time and space depend on tree height h, which is log n for balanced BSTs.

💡 For n=20 balanced nodes, this means about 5 steps instead of 20.

Interview Verdict: Accepted and efficient for balanced BSTs

This approach leverages BST properties to reduce search time significantly.

🧠

Optimal (Iterative BST Search)

💡 This approach avoids recursion stack overhead by iteratively traversing the tree, which is preferred in production code and interviews.

Intuition

Start at root and iteratively move left or right depending on comparison with target until node is found or null is reached.

Algorithm

1. Initialize current node as root.
2. While current node is not null:
3. If current node's value equals target, return current node.
4. If target < current node's value, move to left child.
5. Else, move to right child.
6. If loop ends, target not found; return null.

💡 This approach is efficient and avoids recursion stack, making it suitable for large trees.

</>

Code

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

def searchBST(root, val):
    current = root
    while current:
        if current.val == val:
            return current
        elif val < current.val:
            current = current.left
        else:
            current = current.right
    return None

# Example usage:
root = TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode(7))
result = searchBST(root, 2)
print(result.val if result else 'null')

Line Notes

current = rootStart traversal from root

while current:Loop until we reach a null node

if current.val == val:Check if current node matches target

current = current.leftMove left if target smaller

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

public class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        TreeNode current = root;
        while (current != null) {
            if (current.val == val) return current;
            else if (val < current.val) current = current.left;
            else current = current.right;
        }
        return null;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(4);
        root.left = new TreeNode(2);
        root.right = new TreeNode(7);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(3);
        Solution sol = new Solution();
        TreeNode res = sol.searchBST(root, 2);
        System.out.println(res != null ? res.val : "null");
    }
}

Line Notes

TreeNode current = root;Initialize traversal pointer at root

while (current != null) {Loop until no more nodes

if (current.val == val) return current;Return node if found

else if (val < current.val) current = current.left;Move left if target smaller

#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        TreeNode* current = root;
        while (current) {
            if (current->val == val) return current;
            else if (val < current->val) current = current->left;
            else current = current->right;
        }
        return nullptr;
    }
};

int main() {
    TreeNode* root = new TreeNode(4);
    root->left = new TreeNode(2);
    root->right = new TreeNode(7);
    root->left->left = new TreeNode(1);
    root->left->right = new TreeNode(3);
    Solution sol;
    TreeNode* res = sol.searchBST(root, 2);
    cout << (res ? to_string(res->val) : "null") << endl;
    return 0;
}

Line Notes

TreeNode* current = root;Initialize traversal pointer at root

while (current) {Loop until no more nodes

if (current->val == val) return current;Return node if found

else if (val < current->val) current = current->left;Move left if target smaller

class TreeNode {
    constructor(val=0, left=null, right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function searchBST(root, val) {
    let current = root;
    while (current !== null) {
        if (current.val === val) return current;
        else if (val < current.val) current = current.left;
        else current = current.right;
    }
    return null;
}

const root = new TreeNode(4, new TreeNode(2, new TreeNode(1), new TreeNode(3)), new TreeNode(7));
const result = searchBST(root, 2);
console.log(result ? result.val : 'null');

Line Notes

let current = root;Initialize traversal pointer at root

while (current !== null) {Loop until no more nodes

if (current.val === val) return current;Return node if found

else if (val < current.val) current = current.left;Move left if target smaller

⏱

Complexity

TimeO(h)

SpaceO(1)

Iterative traversal visits nodes along one path from root to leaf, so time depends on height h. Space is constant as no recursion stack is used.

💡 For balanced trees with n=20, this means about 5 steps and minimal memory usage.

Interview Verdict: Accepted and optimal for interview coding

This is the preferred approach in interviews due to its efficiency and iterative style.

📊

All Approaches - One-Glance Tradeoffs

💡 In 95% of interviews, code the recursive BST property search or iterative approach for best balance of clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n)	O(h)	Yes (deep recursion)	N/A	Mention only - never code
2. Recursive BST Property Search	O(h)	O(h)	Yes (deep recursion)	N/A	Good for clarity and accepted in interviews
3. Iterative BST Search	O(h)	O(1)	No	N/A	Optimal approach to code in interviews

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice all approaches, and prepare to explain your reasoning clearly in interviews.

How to Present

Step 1: Clarify the problem and confirm input/output format.Step 2: Describe the brute force approach to show understanding.Step 3: Explain how BST properties allow pruning and implement recursive search.Step 4: Optimize to iterative solution to avoid recursion overhead.Step 5: Test with examples and edge cases.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 7min → Test: 3min. Total ~15min

What the Interviewer Tests

Interviewer tests your understanding of BST properties, recursion vs iteration, and ability to optimize code for time and space.

Common Follow-ups

• What if the BST is unbalanced? → Time complexity degrades to O(n).
• Can you implement an iterative solution? → Yes, to save stack space.

💡 These follow-ups check if you understand the impact of tree shape and can code iteratively.

🔍

Pattern Recognition

When to Use

1) Input is a binary tree with BST property, 2) Need to find a node or value, 3) Target value given, 4) Return node or subtree

Signature Phrases

search in a BSTreturn the subtree rooted with that node

NOT This Pattern When

Searching in a normal binary tree or balanced binary tree without BST property

Similar Problems

Find Minimum in BST - similar traversal using BST propertyValidate BST - uses BST property to check correctness

Practice

1. Consider the following code for finding the lowest common ancestor in a BST. Given the BST below and nodes p=2 and q=8, what value does the function return? BST structure: 6 / \ 2 8 / \ \ 0 4 9 / \ 3 5

easy

A. 2

B. 8

C. 4

D. 6

Solution

1. Step 1: Trace first iteration with current=6

   p=2 and q=8; 2 < 6 and 8 > 6, so current is split point; return 6.

2. Step 2: Confirm no further traversal

   Since p and q lie on different sides of 6, 6 is the LCA.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Split point found at root 6 immediately [OK]

Hint: LCA is where paths to p and q diverge [OK]

Common Mistakes:

• Returning smaller node instead of split point
• Confusing left/right subtree traversal
• Off-by-one error in loop conditions

2. You are given a binary tree where exactly two nodes have been swapped by mistake, violating the binary search tree property. Which approach guarantees an optimal solution to recover the tree without changing its structure or using extra space beyond a constant amount?

easy

A. Use a bottom-up dynamic programming approach to reconstruct the BST by comparing subtrees and swapping nodes.

B. Perform an inorder traversal, store values in a list, sort the list, then overwrite the tree nodes with sorted values.

C. Apply a greedy approach by swapping any two nodes that violate the BST property during a single inorder traversal pass.

D. Use Morris inorder traversal to detect the two swapped nodes during traversal and swap their values, achieving O(1) space complexity.

Solution

1. Step 1: Understand the problem constraints

   The problem requires recovering a BST where two nodes are swapped, without extra space and without changing the tree structure.

2. Step 2: Identify the approach that meets constraints

   Morris inorder traversal allows inorder traversal without recursion or stack, detecting swapped nodes on the fly and swapping their values, achieving O(1) space.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Morris traversal is the only approach with O(1) space and no structural changes [OK]

Hint: Morris traversal enables O(1) space recovery [OK]

Common Mistakes:

• Assuming sorting values is optimal despite extra space
• Believing greedy single pass fixes all cases
• Confusing DP with tree recovery

3. You are given a binary search tree and a value range [low, high]. You need to remove all nodes whose values fall outside this range, ensuring the resulting tree remains a valid BST. Which approach guarantees an optimal solution in terms of time and space complexity?

easy

A. Iteratively prune the BST by adjusting pointers using BST properties without rebuilding the tree.

B. Apply dynamic programming to store subtrees and decide which to keep based on range constraints.

C. Use a greedy approach to remove nodes one by one by checking each node's value and deleting if out of range.

D. Perform an inorder traversal to collect all valid nodes, then rebuild the BST from the sorted list.

Solution

1. Step 1: Understand the problem constraints

   The problem requires trimming nodes outside [low, high] while preserving BST properties efficiently.

2. Step 2: Evaluate approaches

   Rebuilding the tree (A) wastes time and space. Greedy removal (C) is inefficient and may break BST structure. DP (B) is unnecessary and overcomplicates. Iterative pruning (D) leverages BST properties to skip subtrees and adjust pointers in O(n) time and O(1) space.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Iterative pruning uses BST properties optimally [OK]

Hint: Use BST properties to prune iteratively for optimal trimming [OK]

Common Mistakes:

• Rebuilding tree wastes space and time
• Greedy removal breaks BST structure

4. You are given a binary search tree and a target integer k. You need to determine if there exist two distinct nodes in the BST whose values sum up to k. Which of the following approaches guarantees an optimal solution in terms of time and space complexity?

easy

A. Perform an inorder traversal to get a sorted array, then use two pointers to find if a pair sums to k.

B. Use dynamic programming to store sums of all subtree pairs and check for k.

C. Perform a brute force nested traversal of all node pairs directly on the BST without extra storage.

D. Use a greedy approach by always choosing the smallest and largest node values and adjusting pointers.

Solution

1. Step 1: Understand BST property and inorder traversal

   Inorder traversal of a BST produces a sorted array of node values.

2. Step 2: Apply two-pointer technique on sorted array

   Using two pointers at start and end, we can efficiently find if two values sum to k in O(n) time and O(n) space.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Inorder + two pointers is optimal and uses BST ordering [OK]

Hint: Inorder traversal yields sorted array for two-pointer sum [OK]

Common Mistakes:

• Trying nested loops directly on BST nodes without flattening
• Assuming greedy approach works without sorting
• Using DP which is unnecessary here

5. Suppose the BST can contain negative values and duplicates, and you want to convert it to a Greater Tree where each node's new value is the sum of all nodes with values greater than or equal to it. Which modification to the optimal iterative approach is necessary to handle duplicates correctly?

hard

A. Change traversal to inorder (left-root-right) to process duplicates in ascending order.

B. Use a hash map to store counts of each value and update nodes after traversal.

C. Skip nodes with duplicate values during traversal to avoid double counting.

D. During traversal, accumulate sum including nodes with values equal to current node before updating node value.

Solution

1. Step 1: Understand how duplicates affect sum accumulation

   Duplicates must be included in the sum for nodes with equal values to maintain correctness.

2. Step 2: Modify accumulation logic

   Accumulate sum including all nodes with values >= current node before updating node.val during reverse inorder traversal.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Including equal values in sum ensures correct Greater Tree with duplicates [OK]

Hint: Include equal values in sum during reverse inorder traversal [OK]

Common Mistakes:

• Changing traversal order breaks sum logic
• Skipping duplicates causes incorrect sums
• Using extra data structures unnecessarily increases complexity