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. The following code attempts to convert a BST to a Greater Tree using reverse inorder traversal. Identify the line that contains a subtle bug causing incorrect node values.

medium

A. Line 8: node = node.left instead of node = node.right

B. Line 6: while node: loop condition

C. Line 10: acc_sum += node.val accumulation

D. Line 12: node = node.right traversal after updating node

Solution

1. Step 1: Understand traversal order needed

   Reverse inorder traversal requires visiting right subtree first to accumulate greater values.

2. Step 2: Identify incorrect subtree traversal

   Line 8 incorrectly moves to left child first, reversing traversal order and causing wrong sums.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Changing node = node.left to node = node.right fixes traversal order [OK]

Hint: Reverse inorder must traverse right subtree first [OK]

Common Mistakes:

• Swapping left and right subtree traversal order
• Resetting acc_sum inside loops
• Updating node values before traversing right subtree

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. The following code attempts to find if there exist two distinct nodes in a BST whose values sum to k. Identify the line containing the subtle bug that can cause incorrect results.

medium

A. Line 6: dfs(node.left)

B. Line 4: if k - node.val in seen:

C. Line 7: seen.add(node.val)

D. Line 8: dfs(node.right)

Solution

1. Step 1: Understand DFS and set usage

   The code checks if complement exists in seen before adding current node's value.

2. Step 2: Identify bug in order of operations

   Checking complement before adding current node's value misses pairs where both nodes are the same, or misses valid pairs if current node's value is needed for complement checks in children.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Complement check must happen after adding current node's value to seen [OK]

Hint: Add current node to set before checking complements [OK]

Common Mistakes:

• Checking complement before adding current node's value
• Not handling None nodes properly
• Returning False too early

4. Suppose the input array can contain duplicate values and you want to build a height-balanced BST that allows duplicates on the right subtree. Which modification to the optimal approach is correct?

hard

A. Change mid calculation to always pick the left middle element to ensure duplicates go to the right subtree.

B. Change the recursive calls to insert duplicates always into the left subtree to maintain balance.

C. Keep mid calculation as is, but when inserting duplicates, always place them in the right subtree during tree construction.

D. Use the brute force approach inserting elements one by one to handle duplicates correctly.

Solution

1. Step 1: Understand duplicate handling

   Duplicates should be consistently placed in the right subtree to maintain BST property.

2. Step 2: Modify insertion logic

   Keep mid calculation unchanged for balance; during node creation, ensure duplicates go to right subtree by design.

3. Step 3: Avoid brute force

   Brute force insertion leads to unbalanced trees and higher complexity.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Maintain balance and BST property by consistent duplicate placement right [OK]

Hint: Keep mid; place duplicates right during construction [OK]

Common Mistakes:

• Changing mid breaks balance
• Inserting duplicates left breaks BST property

5. Suppose you want to modify the BST insertion algorithm to allow inserting duplicate values by always inserting duplicates into the left subtree. Which of the following changes to the iterative insertion code below correctly implements this behavior without breaking the BST property?

def insertIntoBST(root, val):
    if root is None:
        return TreeNode(val)
    curr = root
    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

hard

A. Change the condition to if val <= curr.val: and insert duplicates to the left subtree.

B. Change the condition to if val < curr.val: and insert duplicates to the right subtree.

C. Always insert duplicates as new root nodes to maintain BST property.

D. Disallow duplicates by returning the original tree without insertion.

Solution

1. Step 1: Understand duplicate insertion rule

   Duplicates must go to the left subtree, so values equal to current node should be treated as less or equal.

2. Step 2: Modify comparison operator

   Changing condition to val <= curr.val ensures duplicates follow left subtree insertion path, preserving BST property.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Duplicates inserted left by using <= comparison [OK]

Hint: Use <= to direct duplicates left, preserving BST order [OK]

Common Mistakes:

• Inserting duplicates right breaks problem requirement
• Inserting duplicates as new roots breaks BST
• Ignoring duplicates causes infinite recursion