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. Given the following code for inserting a value into a BST, what will be the value of the variable parent.val when inserting 5 into the BST rooted at 4 with left child 2 and right child 7?

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

def insertIntoBST(root, val):
    if root is None:
        return TreeNode(val)
    curr = root
    parent = None
    while curr:
        parent = curr
        if val < curr.val:
            if curr.left is None:
                curr.left = TreeNode(val)
                return root
            curr = curr.left
        else:
            if curr.right is None:
                curr.right = TreeNode(val)
                return root
            curr = curr.right
    return root

root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(7)
val = 5
insertIntoBST(root, val)

easy

A. 4

B. 7

C. 2

D. 5

Solution

1. Step 1: Trace insertion path

   Start at root (4). Since 5 > 4, move right to node 7. Update parent to 4.

2. Step 2: Check right child of 7

   5 < 7, so move left. Left child of 7 is None, so insert here. Parent is now 7, but last parent before insertion was 4.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Parent is last non-null node before insertion -> 4 [OK]

Hint: Parent tracks last node before insertion point [OK]

Common Mistakes:

• Confusing parent with current node
• Off-by-one in loop iteration
• Mistaking inserted value as parent

2. 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

3. What is the time complexity of the optimal divide-and-conquer approach to convert a sorted array of length n into a height-balanced BST, and why?

medium

A. O(n log n), because each recursive call processes half the array and builds subtrees.

B. O(n), because each element is visited exactly once to create nodes without extra overhead.

C. O(n^2), because the recursion tree has n levels and each level processes n elements.

D. O(log n), because the tree height is log n and only root nodes are created at each level.

Solution

1. Step 1: Analyze recursion calls

   The algorithm visits each element exactly once to create a TreeNode, splitting the array into halves recursively.

2. Step 2: Calculate total work

   Each element is processed once, so total time is proportional to n.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Single pass over array with divide-and-conquer -> O(n) time [OK]

Hint: Each element processed once -> O(n) time [OK]

Common Mistakes:

• Confusing recursion depth with total work
• Assuming O(n log n) due to recursion

4. Consider the following buggy code for trimming a BST. Which line contains the subtle bug that can cause the resulting tree to violate BST properties or cause runtime errors?

medium

A. Line 3: root = root.left when root.val < low

B. Line 5: root = root.left when root.val > high

C. Line 10: cur.left = cur.left.right inside left subtree trimming

D. Line 16: cur.right = cur.right.left inside right subtree trimming

Solution

1. Step 1: Check root adjustment logic

   If root.val < low, root should move to root.right, not root.left, to find valid nodes.

2. Step 2: Verify other lines

   Line 5 correctly moves root to root.left if root.val > high. Lines 10 and 16 correctly adjust subtree pointers.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Incorrect pointer move causes invalid pruning or infinite loop [OK]

Hint: Root moves wrong direction when value < low [OK]

Common Mistakes:

• Confusing left and right subtree moves
• Incorrect pointer updates causing invalid BST

5. What is the time and space complexity of the optimal inorder traversal BST validation algorithm for a tree with n nodes and height h?

medium

A. Time O(n), Space O(h) due to recursion stack where h is tree height

B. Time O(n log n), Space O(n) due to storing all nodes

C. Time O(n^2), Space O(1) because no extra data structures are used

D. Time O(n), Space O(n) because all nodes are stored during traversal

Solution

1. Step 1: Identify time complexity

   The algorithm visits each node exactly once in inorder traversal, so time is O(n).

2. Step 2: Identify space complexity

   Space is O(h) due to recursion stack, where h is the height of the tree; no extra arrays store all nodes.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Linear time and stack space proportional to tree height [OK]

Hint: Inorder traversal visits each node once, stack depth = tree height [OK]

Common Mistakes:

• Confusing recursion stack space with storing all nodes
• Assuming O(n log n) due to sorting
• Ignoring recursion stack space