Search in a BST

📋

Problem

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.

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

Edge cases: Searching for the root node value → should return entire treeSearching for a leaf node value → should return that leaf nodeSearching for a value smaller than all nodes → should return null

</>

IDE

def searchBST(root: TreeNode, val: int) -> TreeNode:public TreeNode searchBST(TreeNode root, int val)TreeNode* searchBST(TreeNode* root, int val)function searchBST(root, val)

def searchBST(root, val):
    # Write your solution here
    pass

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        // Write your solution here
        return null;
    }
}

#include <vector>
using namespace std;

TreeNode* searchBST(TreeNode* root, int val) {
    // Write your solution here
    return nullptr;
}

function searchBST(root, val) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: null for existing nodeNot checking current node's value before recursing or returning null prematurely.✅ Add condition: if root.val == val: return root before recursive calls.

Wrong: subtree rooted at wrong nodeReturning subtree from incorrect node due to wrong comparison or traversal direction.✅ Use BST property: if val < root.val recurse left, else recurse right; return node only if root.val == val.

Wrong: non-null subtree for value not in treeNot returning null when reaching leaf null child or searching both subtrees unnecessarily.✅ Return null when root is null; do not search both left and right subtrees.

Wrong: TLE on large inputUsing full tree traversal instead of BST property pruning.✅ Implement search using BST property to prune search path to O(h) time.

✓

Test Cases

Try testing your code on smallest trees and null cases to catch base case bugs.

Think about common pitfalls like searching both subtrees or stopping early incorrectly.

Focus on optimizing your search to avoid full tree traversal for large inputs.

t1_01basic

Input{"root":[4,2,7,1,3],"val":2}

Expected[2,1,3]

⏱ Performance - must finish in 2000ms

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

💡 Recall that BST search uses the property that left subtree nodes are smaller and right subtree nodes are larger.

💡 Check if current node's value equals val; if not, decide to go left or right based on comparison.

💡 Return the subtree rooted at the found node or null if not found.

Why it failed: Returned wrong subtree or null for existing node. Fix by correctly comparing node values and returning subtree rooted at matched node.

✓ Correctly found and returned the subtree rooted at the searched value.

t1_02basic

Input{"root":[5,3,6,2,4,null,7],"val":4}

Expected[4]

⏱ Performance - must finish in 2000ms

The node with value 4 is found as a leaf node with no children.

💡 Leaf nodes have no children; search should return the node itself if found.

💡 Ensure your search correctly navigates left or right subtree based on val comparison.

💡 Return the node with value 4 as a subtree with no children.

Why it failed: Returned null or incorrect subtree for leaf node. Fix by correctly traversing BST and returning node when found.

✓ Correctly returned the leaf node subtree.

t2_01edge

Input{"root":[10],"val":10}

Expected[10]

⏱ Performance - must finish in 2000ms

Single node tree where searched value is the root node.

💡 Test the simplest tree with only one node.

💡 Check if root node's value matches val and return root if yes.

💡 Return the root node as the subtree.

Why it failed: Fails to return root when tree has single node matching val. Fix by checking root node value before recursion.

✓ Correctly returns the root node in single-node tree.

t2_02edge

Input{"root":[8,3,10,1,6,null,14,null,null,4,7,13],"val":1}

Expected[1]

⏱ Performance - must finish in 2000ms

Searching for a leaf node value 1, which has no children.

💡 Leaf nodes have no children; search should return the node itself if found.

💡 Ensure traversal correctly reaches leaf nodes.

💡 Return the leaf node subtree with no children.

Why it failed: Fails to find leaf node or returns incorrect subtree. Fix by correctly traversing BST and returning node when found.

✓ Correctly returns the leaf node subtree.

t2_03edge

Input{"root":[5,3,6,2,4,null,7],"val":1}

Expectednull

⏱ Performance - must finish in 2000ms

Searching for a value smaller than all nodes in the BST returns null.

💡 If val is less than all nodes, search should eventually reach a null child.

💡 Check for null nodes to stop recursion or iteration.

💡 Return null when val is not found in the BST.

Why it failed: Returns non-null subtree for non-existent smaller value. Fix by returning null when traversal reaches null node.

✓ Correctly returns null for value smaller than all nodes.

t3_01corner

Input{"root":[5,3,6,2,4,null,7],"val":8}

Expectednull

⏱ Performance - must finish in 2000ms

Searching for a value larger than all nodes returns null, testing correct boundary traversal.

💡 Check that search moves right subtree when val > node.val.

💡 Ensure traversal stops at null when val not found.

💡 Return null if val is not present in BST.

Why it failed: Incorrectly returns a subtree or non-null for value larger than all nodes. Fix by returning null when traversal reaches null.

✓ Correctly returns null for value larger than all nodes.

t3_02corner

Input{"root":[10,5,15,3,7,null,18],"val":7}

Expected[7]

⏱ Performance - must finish in 2000ms

Tests that search does not confuse 0/1 traversal with unbounded search; must not revisit nodes unnecessarily.

💡 BST search should not revisit nodes once direction chosen.

💡 Avoid searching both left and right subtrees unnecessarily.

💡 Return node immediately when found without extra traversal.

Why it failed: Search revisits both subtrees causing inefficiency or wrong result. Fix by using BST property to choose one subtree only.

✓ Correctly uses BST property to find node without extra traversal.

t3_03corner

Input{"root":[20,10,30,5,15,25,35],"val":15}

Expected[15]

⏱ Performance - must finish in 2000ms

Greedy trap test: ensures search does not stop prematurely at wrong node.

💡 Do not stop search at first node greater than val.

💡 Check node.val == val exactly before returning.

💡 Continue search in correct subtree until node found or null.

Why it failed: Returns wrong node because of greedy stopping at first larger node. Fix by checking equality before returning.

✓ Correctly finds node by exact match, avoiding greedy trap.

t4_01performance

Input{"root":[50000,25000,75000,12500,37500,62500,87500,6250,18750,31250,43750,56250,68750,81250,93750,3125,9375,15625,21875,28125,34375,40625,46875,53125,59375,65625,71875,78125,84375,90625,96875,1562,4687,7812,10937,14062,17187,20312,23437,26562,29687,32812,35937,39062,42187,45312,48437,51562,54687,57812,60937,64062,67187,70312,73437,76562,79687,82812,85937,89062,92187,95312,98437,781,2343,3906,5468,7031,8593,10156,11718,13281,14843,16406,17968,19531,21093,22656,24218,25781,27343,28906,30468,32031,33593,35156,36718,38281,39843,41406,42968,44531,46093,47656,49218,50781,52343,53906,55468,57031,58593,60156,61718,63281,64843,66406,67968,69531,71093,72656,74218,75781,77343,78906,80468,82031,83593,85156,86718,88281,89843,91406,92968,94531,96093,97656,99218],"val":78906}

Expected[78906]

⏱ Performance - must finish in 2000ms

Large balanced BST with 127 nodes (complete binary tree of height 7), searching for a value that exists near the bottom to test O(h) complexity within 2 seconds.

💡 BST search runs in O(h) time where h is tree height, not O(n).

💡 Use iterative or recursive BST property search to avoid TLE.

💡 Avoid full tree traversal; prune search path using BST properties.

Why it failed: TLE due to full tree traversal or inefficient search. Fix by using BST property to prune search path to O(h).

✓ Search runs in O(h) time confirming efficient BST search implementation.

Practice

1. Given the following code snippet for converting a sorted array to a height-balanced BST, what is the value of the root node's value after the first call to helper with input nums = [1, 3, 5]?

easy

A. 3

B. 1

C. 5

D. None

Solution

1. Step 1: Calculate mid index for initial call

   For nums=[1,3,5], left=0, right=2, mid=(0+2)//2=1.

2. Step 2: Identify root value

   nums[mid] = nums[1] = 3, so root node value is 3.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Mid index calculation picks 3 as root [OK]

Hint: Mid index picks middle element as root [OK]

Common Mistakes:

• Choosing first or last element as root
• Off-by-one mid calculation

2. Given the following code for finding the kth smallest element in a BST, what is the returned value when called with k=2 on the provided tree?

from typing import Optional

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

def kthSmallest(root: Optional[TreeNode], k: int) -> int:
    stack = []
    current = root
    count = 0

    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        count += 1
        if count == k:
            return current.val
        current = current.right

# Tree:
#     3
#    / \
#   1   4
#    \
#     2

root = TreeNode(3)
root.left = TreeNode(1)
root.right = TreeNode(4)
root.left.right = TreeNode(2)
print(kthSmallest(root, 2))

easy

A. 3

B. 1

C. 2

D. 4

Solution

1. Step 1: Trace the inorder traversal steps

   Stack initially empty, current=root(3). Push 3, move left to 1. Push 1, move left to None. Pop 1 (count=1), move right to 2.

2. Step 2: Continue traversal to find kth=2

   Push 2, move left None. Pop 2 (count=2), return 2 as kth smallest.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Second smallest in BST is 2 [OK]

Hint: Inorder traversal visits nodes in ascending order [OK]

Common Mistakes:

• Off-by-one counting of k
• Returning before incrementing count

3. Given the following code for trimming a BST and the input tree with root value 3, left child 1, right child 4, and low=2, high=3, what is the value of the root node after trimming?

easy

A. 2

B. 3

C. 1

D. 4

Solution

1. Step 1: Move root to valid range

   Root=3 is within [2,3], so no change.

2. Step 2: Trim left subtree

   Left child=1 < 2, so replace left child with its right subtree (None). Left child becomes None.

3. Step 3: Trim right subtree

   Right child=4 > 3, so replace right child with its left subtree (None). Right child becomes None.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Root remains 3 with no children after trimming [OK]

Hint: Check root adjustment before subtree trimming [OK]

Common Mistakes:

• Assuming root changes when already in range
• Forgetting to trim subtrees correctly

4. The following code attempts to recover a BST with two swapped nodes using Morris traversal. Identify the line containing the subtle bug that causes incorrect recovery when the swapped nodes are adjacent in inorder traversal.

def recoverTree(root):
    first = second = prev = None
    current = root
    while current:
        if not current.left:
            if prev and prev.val > current.val:
                if not first:
                    first = prev
                    second = current
                else:
                    second = current
            prev = current
            current = current.right
        else:
            pred = current.left
            while pred.right and pred.right != current:
                pred = pred.right
            if not pred.right:
                pred.right = current
                current = current.left
            else:
                pred.right = None
                if prev and prev.val > current.val:
                    if not first:
                        first = prev
                        second = current
                    else:
                        second = current
                prev = current
                current = current.right
    first.val, second.val = second.val, first.val

medium

A. Swapping values at the end without checking if both nodes are found

B. Line setting second = current inside the first if condition

C. Line setting first = prev inside the second if condition

D. Line setting first = prev inside the first if condition

Solution

1. Step 1: Analyze detection of swapped nodes

   The code sets first and second whenever a violation is found, but overwrites them without preserving the first violation's first node.

2. Step 2: Identify the bug in swapping

   The swap at the end assumes both first and second are found, but if only one violation is detected (adjacent nodes swapped), second may be incorrect or null, causing wrong swap.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Swapping without confirming both nodes leads to incorrect recovery in adjacent swaps [OK]

Hint: Must confirm both nodes before swapping values [OK]

Common Mistakes:

• Overwriting first and second on multiple violations
• Swapping values prematurely after first violation
• Not restoring tree structure after Morris traversal

5. Suppose the BST can contain duplicate values and you want to find the kth smallest element counting duplicates as separate elements. Which modification to the iterative inorder traversal approach correctly handles duplicates without extra space or preprocessing?

hard

A. Perform a full inorder traversal collecting all values, then remove duplicates before indexing kth element.

B. Modify the traversal to skip nodes with duplicate values to avoid counting duplicates multiple times.

C. Use a hash set to track visited values and only increment count for unique values.

D. Keep the traversal unchanged; duplicates are naturally counted separately in inorder traversal order.

Solution

1. Step 1: Understand duplicates in BST inorder traversal

   Inorder traversal visits nodes in sorted order including duplicates as separate nodes.

2. Step 2: Check if modification is needed

   Since duplicates appear as separate nodes, counting each node visited naturally counts duplicates separately without extra logic.

3. Step 3: Evaluate other options

   Skipping duplicates (B) or using a hash set (C) changes semantics. Removing duplicates after full traversal (D) is inefficient and breaks counting duplicates separately.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Inorder traversal inherently counts duplicates separately [OK]

Hint: Duplicates appear as separate nodes in inorder traversal [OK]

Common Mistakes:

• Trying to skip duplicates
• Using extra space unnecessarily
• Assuming duplicates must be merged