What happens if you ignoring bst property and searching both subtrees?

Code runs slower, time complexity degrades to O(n) Fix: Use BST property to decide which subtree to search

What happens if you not handling null nodes properly?

Runtime errors or infinite recursion Fix: Always check if current node is null before accessing its value

What happens if you returning wrong node or subtree?

Incorrect output, partial subtree or wrong node returned Fix: Return the node where value matches exactly, not just a partial match

Interview Prepbinary-search-treeseasyAmazonGoogle

Search in a BST

Choose your preparation mode3 modes available

Try It Solution Trace

🎯

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

Start at the root node.
If the current node is null, return null (not found).
If the current node's value equals the target, return the current node.
Recursively search the left subtree; if found, return the result.
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.

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

Search in a BST

Intuition

Algorithm

Intuition

Algorithm

Intuition

Algorithm

How to Present

Time Allocation

What the Interviewer Tests

Common Follow-ups

When to Use

Signature Phrases

NOT This Pattern When

Similar Problems