Search in a BST

▶

Steps

setup

Initialize current node to root

The algorithm starts by setting the current node pointer to the root of the BST, which has value 4.

💡 Starting at the root is essential because the BST property applies from the root downward.

Line:

current = root

💡 The search begins at the top of the tree where all values are accessible through BST properties.

compare

Compare current node value with target

The algorithm compares the current node's value (4) with the target value (2).

💡 This comparison determines the next direction to move in the BST.

Line:

if current.val == val:

💡 Since the values are not equal, the algorithm must decide to go left or right.

compare

Decide to move left because target < current node value

Since 2 is less than 4, the algorithm decides to move to the left child of the current node.

💡 BST property: smaller values are in the left subtree, so search moves left.

Line:

elif val < current.val:
    current = current.left

💡 The search space is reduced by moving left, ignoring the right subtree.

compare

Compare current node value with target again

Now at node with value 2, the algorithm compares it to the target value 2.

💡 Each node visited is checked for equality with the target.

Line:

if current.val == val:

💡 The target node is found, so the search can stop.

return

Return the found node

The algorithm returns the current node (value 2) as the search result.

💡 Returning the node allows access to its entire subtree.

Line:

return current

💡 The search result includes the subtree rooted at the found node.

traverse

Traversal of found subtree: mark node 2 as root of result

The subtree rooted at node 2 includes nodes 1 and 3 as children, which are part of the returned subtree.

💡 Understanding the returned subtree helps visualize the search output.

Line:

N/A - conceptual subtree return

💡 The returned node includes all descendants, representing the subtree.

prune

Confirm no further search needed

Since the target node is found, the algorithm does not continue searching other branches.

💡 BST search stops early once the target is found, improving efficiency.

Line:

N/A - loop exit after return

💡 Early termination is a key efficiency feature of BST search.

reconstruct

Final output subtree ready

The algorithm outputs the subtree rooted at node 2, containing nodes 1 and 3 as children.

💡 The returned subtree represents the search result as required by the problem.

Line:

N/A - return value used by caller

💡 The subtree structure is preserved in the output.

return

End of search

The search is complete with the target node found and returned.

💡 The algorithm terminates successfully with the correct subtree.

Line:

N/A - function end

💡 The search process is efficient and terminates as soon as the target is found.

final

Summary: Search path and result

The search path visited nodes 4 then 2, found the target, and returned the subtree rooted at 2.

💡 Reviewing the path and result consolidates understanding of BST search.

Line:

N/A - summary step

💡 The search path is minimal and directed by BST properties, demonstrating efficiency.

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  # STEP 1: Initialize current to root
    while current:  # STEP 2: Loop while current is not None
        if current.val == val:  # STEP 4: Check if current node is target
            return current  # STEP 5: Return current node if found
        elif val < current.val:  # STEP 3: Decide to go left if target less
            current = current.left  # STEP 6: Move current to left child
        else:
            current = current.right  # STEP 7: Move current to right child
    return None  # STEP 8: Return None if not found

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

📊

Search in a BST - Watch the Algorithm Execute, Step by Step

Watching each comparison and pointer movement helps you understand how BST properties guide the search efficiently without exploring unnecessary nodes.

Current node: 1

42713

Current node: 1

42713

Current node: 2

42713

Current node: 2

42713

Return: 2

Current node: 2

42713

Return: 2

Current node: 2

42713

Result: [2, 1, 3]

Return: 2

42713

Result: [2, 1, 3]

Return: 2

42713

Result: [2, 1, 3]

Return: 2

42713

Result: [2, 1, 3]

Return: 2

42713

Result: [2, 1, 3]

Return: 2

Key Takeaways

✓ BST search efficiently narrows down the search space by comparing target with current node and moving left or right accordingly.

This insight is hard to see from code alone because the pruning effect is visual and depends on tree structure.

✓ The search terminates immediately upon finding the target node, returning the subtree rooted at that node.

Understanding early termination helps grasp why BST search is faster than traversing the entire tree.

✓ Each step's comparison and pointer movement is a deliberate decision guided by BST ordering properties.

Seeing each pointer move clarifies how the algorithm avoids unnecessary nodes.

Practice

1. Consider the following Python code implementing BST validation using inorder traversal. What is the output of the program when run with the given test cases?

easy

A. true followed by false

B. true followed by true

C. false followed by true

D. false followed by false

Solution

1. Step 1: Trace first tree (2,1,3)

   Inorder traversal yields [1,2,3], strictly increasing, so returns true.

2. Step 2: Trace second tree (5,1,4 with children 3 and 6)

   Inorder traversal yields [1,5,3,4,6], 3 < 5 violates BST property, so returns false.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   First tree valid BST, second invalid due to subtree violation [OK]

Hint: Inorder traversal must be strictly increasing [OK]

Common Mistakes:

• Assuming subtree root comparison is enough
• Confusing output order
• Missing strict inequality check

2. Consider the following buggy code snippet for converting a sorted array to a height-balanced BST. Which line contains the subtle bug that can cause infinite recursion or stack overflow?

medium

A. Line 5: left_child = self.helper(nums, left, mid - 1)

B. Line 3: mid = (left + right) // 2

C. Line 7: root.right = self.helper(nums, mid + 1, right)

D. Line 2: if left >= right: return None

Solution

1. Step 1: Understand base case condition

   The base case should be when left > right, not left >= right, to allow single-element subarrays.

2. Step 2: Consequence of incorrect base case

   Using left >= right causes the recursion to skip processing subarrays of size 1, leading to infinite recursion or missing nodes.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Base case must allow left == right to process single elements [OK]

Hint: Base case must be left > right, not left >= right [OK]

Common Mistakes:

• Incorrect base case causing infinite recursion
• Misplaced mid calculation

3. What is the worst-case time complexity of the optimized recursive BST node deletion algorithm that uses the in-order successor to replace a node with two children?

medium

A. O(h) where h is the height of the BST

B. O(h^2) due to recursive calls and successor search

C. O(log n) always, since BST is balanced

D. O(n) where n is the total number of nodes in the BST

Solution

1. Step 1: Identify height-based operations

   Deletion involves searching down the tree (O(h)) and finding the in-order successor, which is also O(h) in worst case.

2. Step 2: Combine operations and recursion

   Successor search and recursive deletion happen along a path of length h, so total time is O(h), not O(h^2).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Time proportional to tree height, not total nodes or squared height [OK]

Hint: Deletion time depends on tree height, not total nodes [OK]

Common Mistakes:

• Assuming balanced BST always (log n)
• Confusing recursion depth with squared complexity
• Thinking successor search adds extra factor

4. Suppose the problem is extended so that multiple pairs of nodes (more than two nodes) are swapped in the BST, possibly non-adjacent. Which of the following modifications to the recovery algorithm is correct and efficient?

hard

A. Use the Morris inorder traversal to detect all violations and store all nodes involved, then sort their values and reassign in inorder traversal.

B. Run the Morris traversal multiple times, each time swapping the first detected violation nodes until no violations remain.

C. Use the brute force approach: inorder traversal to collect all values, sort them, then overwrite the tree nodes in inorder traversal.

D. Modify the Morris traversal to swap nodes immediately upon detecting each violation without storing nodes, fixing all swaps in one pass.

Solution

1. Step 1: Understand the problem extension

   Multiple pairs of nodes swapped means multiple violations, possibly complex to detect and fix in one pass.

2. Step 2: Evaluate approaches

   Morris traversal detects only two nodes swapped optimally; multiple swaps require collecting all values, sorting, and rewriting nodes, which brute force does efficiently.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Brute force approach handles multiple swaps correctly by sorting all values [OK]

Hint: Multiple swaps require full value sorting and rewriting [OK]

Common Mistakes:

• Assuming Morris traversal can fix multiple swaps in one pass
• Trying to swap nodes immediately without full detection
• Running multiple passes of Morris traversal inefficiently

5. Suppose the BST can contain duplicate values and you want to find if there exist two nodes (not necessarily distinct) whose values sum to k. Which modification to the optimal inorder + two-pointer approach correctly handles this scenario?

hard

A. Perform inorder traversal and remove duplicates before applying two-pointer technique.

B. Use the same two-pointer approach but allow left and right pointers to point to the same index.

C. Use a hash set to store values and check complements, ignoring duplicates.

D. During two-pointer traversal, if left == right, check if the value at that index appears at least twice in the BST.

Solution

1. Step 1: Understand duplicates and two-pointer constraints

   Two-pointer approach requires two distinct indices; if pointers meet, need to verify if duplicate values exist.

2. Step 2: Modify check when left == right

   Check if the value at that index occurs at least twice in the BST to allow sum with itself.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Only During two-pointer traversal, if left == right, check if the value at that index appears at least twice in the BST. correctly handles duplicates without breaking two-pointer logic [OK]

Hint: Check duplicates count when pointers meet [OK]

Common Mistakes:

• Allowing pointers to be equal without duplicate check
• Removing duplicates loses valid pairs
• Ignoring duplicates in hash set approach