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

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. The following code attempts to implement a BST Iterator using the Morris traversal technique. Identify the bug that can cause the tree structure to remain corrupted after iteration.

class BSTIterator:
    def __init__(self, root):
        self.current = root
        self.next_val = None
        self._advance()

    def _advance(self):
        while self.current:
            if not self.current.left:
                self.next_val = self.current.val
                self.current = self.current.right
                return
            else:
                pre = self.current.left
                while pre.right and pre.right != self.current:
                    pre = pre.right
                if not pre.right:
                    pre.right = self.current
                    self.current = self.current.left
                else:
                    # BUG: Missing restoration of thread
                    self.next_val = self.current.val
                    self.current = self.current.right

medium

A. Line resetting pre.right to null is missing, so threads are not removed.

B. Line setting self.next_val = self.current.val is incorrect and should be removed.

C. Line moving self.current to self.current.left should be self.current.right instead.

D. Line initializing self.current = root in __init__ is incorrect and should be null.

Solution

1. Step 1: Identify thread restoration step

   In Morris traversal, after visiting a node, the temporary thread (pre.right) must be reset to null to restore the tree.

2. Step 2: Locate missing restoration

   The code omits resetting pre.right = None in the else block, causing the tree to remain modified after iteration.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing thread removal corrupts tree structure [OK]

Hint: Always restore threads to avoid tree corruption [OK]

Common Mistakes:

• Forgetting to remove threads
• Misplacing next_val assignment
• Incorrect current pointer updates

4. The following code attempts to compute the range sum of a BST using iterative DFS with pruning. Identify the line containing the subtle bug that causes incorrect results or inefficiency.

medium

A. Line that appends node.left when node.val < low

B. Line that pops node from stack

C. Line that adds node.val to total

D. Line that appends node.right when node.val is in range

Solution

1. Step 1: Understand pruning logic

   If node.val < low, left subtree nodes are smaller and cannot be in range, so left subtree should be skipped.

2. Step 2: Identify incorrect line

   Appending node.left when node.val < low causes unnecessary traversal of left subtree, violating pruning. It should append node.right instead.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Correct pruning requires appending node.right only when node.val < low [OK]

Hint: Prune left subtree if node.val < low [OK]

Common Mistakes:

• Appending wrong subtree when pruning
• Forgetting to check null nodes

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