Two Sum IV in BST

▶

Steps

setup

Initialize root and empty array for inorder traversal

We start with the root node of the BST and an empty array to store the inorder traversal result.

💡 Setting up the array is essential to collect node values in sorted order via inorder traversal.

Line:

arr = []

💡 The array will hold the BST values in ascending order after traversal.

traverse

Enter inorder traversal at root (5)

Start inorder traversal by entering the root node 5, preparing to traverse its left subtree first.

💡 Inorder traversal visits left subtree before the node itself, so we first go left.

Line:

inorder(root.left, arr)

💡 Traversal is recursive and depth-first, starting at the leftmost node.

traverse

Traverse left subtree of node 5 to node 3

Move down to the left child node 3 to continue inorder traversal.

💡 We keep going left to reach the smallest values first.

Line:

inorder(root.left, arr)

💡 The traversal stack grows as we go deeper into left children.

traverse

Traverse left subtree of node 3 to node 2

Continue left traversal to node 2, the left child of 3.

💡 Leftmost nodes are visited first in inorder traversal.

Line:

inorder(root.left, arr)

💡 We reach the smallest node in this subtree, ready to append its value.

fill_cells

Append node 2 value to array

Node 2 has no left child, so we append its value 2 to the array.

💡 Appending node values in inorder ensures the array is sorted.

Line:

arr.append(root.val)

💡 The first value in the sorted array is 2, the smallest in the BST.

traverse

Return from node 2 and traverse right subtree (none)

Node 2 has no right child, so we return to node 3 to process it.

💡 After left and node visit, inorder goes to right subtree.

Line:

inorder(root.right, arr)

💡 Traversal backtracks to parent after finishing left subtree.

fill_cells

Append node 3 value to array

After finishing left subtree, append node 3's value to the array.

💡 Appending node values in inorder ensures sorted order.

Line:

arr.append(root.val)

💡 The array now contains [2, 3], continuing sorted order.

traverse

Traverse right subtree of node 3 to node 4

Move to the right child of node 3, which is node 4, to continue inorder traversal.

💡 After visiting a node, inorder traversal visits its right subtree.

Line:

inorder(root.right, arr)

💡 Traversal continues to the next higher value node in the BST.

fill_cells

Append node 4 value to array

Node 4 has no left child, so append its value 4 to the array.

💡 Appending node values in inorder ensures sorted order.

Line:

arr.append(root.val)

💡 The array now contains [2, 3, 4], continuing sorted order.

fill_cells

Return to node 5 and append its value

After finishing left subtree of 5, append node 5's value to the array.

💡 Node values are appended after left subtree is fully traversed.

Line:

arr.append(root.val)

💡 The array now contains [2, 3, 4, 5], continuing sorted order.

traverse

Traverse right subtree of node 5 to node 6

Move to the right child of node 5, which is node 6, to continue inorder traversal.

💡 After processing a node, inorder traversal visits its right subtree.

Line:

inorder(root.right, arr)

💡 Traversal continues to the next higher value node in the BST.

fill_cells

Append node 6 value to array (no left child)

Node 6 has no left child, so append its value 6 to the array.

💡 Appending node values in inorder ensures sorted order.

Line:

arr.append(root.val)

💡 The array now contains [2, 3, 4, 5, 6], continuing sorted order.

traverse

Traverse right subtree of node 6 to node 7

Move to the right child of node 6, which is node 7, to continue inorder traversal.

💡 After visiting a node, inorder traversal visits its right subtree.

Line:

inorder(root.right, arr)

💡 Traversal continues to the next higher value node in the BST.

fill_cells

Append node 7 value to array

Node 7 has no left child, so append its value 7 to the array.

💡 Appending node values in inorder ensures sorted order.

Line:

arr.append(root.val)

💡 The array now contains [2, 3, 4, 5, 6, 7], the full sorted list of BST values.

setup

Initialize two pointers for two-sum search

After inorder traversal, initialize left pointer at start (0) and right pointer at end (5) of the sorted array.

💡 Two pointers allow efficient search for two values summing to k.

Line:

left, right = 0, len(arr) - 1

💡 Pointers start at the smallest and largest values in the array.

compare

Check sum of values at pointers (2 + 7)

Calculate sum of values at left (2) and right (7) pointers: 2 + 7 = 9.

💡 Comparing sum to target k determines pointer movement.

Line:

s = arr[left] + arr[right]

💡 Sum equals target, so the pair is found.

from typing import Optional, List

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

def inorder(root: Optional[TreeNode], arr: List[int]) -> None:
    if root is None:
        return
    inorder(root.left, arr)  # STEP: traverse left subtree
    arr.append(root.val)      # STEP: append current node value
    inorder(root.right, arr) # STEP: traverse right subtree

def findTarget(root: Optional[TreeNode], k: int) -> bool:
    arr = []
    inorder(root, arr)        # STEP: get sorted array from BST
    left, right = 0, len(arr) - 1  # STEP: initialize two pointers
    while left < right:
        s = arr[left] + arr[right]  # STEP: compute sum
        if s == k:
            return True             # STEP: found target sum
        elif s < k:
            left += 1              # STEP: move left pointer right
        else:
            right -= 1             # STEP: move right pointer left
    return False                    # STEP: no pair found

📊

Two Sum IV in BST - Watch the Algorithm Execute, Step by Step

Watching the algorithm step-by-step reveals how the BST structure is leveraged to produce a sorted array and how the two-pointer method efficiently finds the target sum without extra tree traversals.

536247

Current node: 0

536247

DFS Stack

0 (entered)

Current node: 1

536247

DFS Stack

1 (entered)0 (left_done)

Current node: 2

532467

DFS Stack

2 (entered)1 (left_done)0 (left_done)

Current node: 2

532467

DFS Stack

2 (returning)1 (left_done)0 (left_done)

Result: [2]

Current node: 1

532467

DFS Stack

1 (entered)0 (left_done)

Result: [2]

Current node: 1

532467

DFS Stack

1 (returning)0 (left_done)

Result: [2, 3]

Current node: 4

532467

DFS Stack

1 (right_done)0 (left_done)

Result: [2, 3]

Current node: 4

532467

DFS Stack

1 (returning)0 (left_done)

Result: [2, 3, 4]

Current node: 0

532467

DFS Stack

0 (returning)

Result: [2, 3, 4, 5]

Current node: 2

532467

DFS Stack

2 (entered)

Result: [2, 3, 4, 5]

Current node: 2

532467

DFS Stack

2 (returning)

Result: [2, 3, 4, 5, 6]

Current node: 5

532467

DFS Stack

5 (entered)

Result: [2, 3, 4, 5, 6]

Current node: 5

532467

DFS Stack

5 (returning)

Result: [2, 3, 4, 5, 6, 7]

Result: [2, 3, 4, 5, 6, 7]

Result: [2, 3, 4, 5, 6, 7]

Return: true

Key Takeaways

✓ Inorder traversal of a BST produces a sorted array of node values.

This insight is hard to see from code alone because recursion and tree structure hide the order of node visits.

✓ The two-pointer technique efficiently finds two numbers summing to k in a sorted array.

Visualizing pointer movements clarifies why moving left or right pointer depends on the sum comparison.

✓ The algorithm stops immediately when the target sum is found, avoiding unnecessary checks.

Seeing the exact step where sum equals k helps understand early termination in search.

Practice

1. You are given a binary search tree and two integers low and high. You need to find the sum of all node values within the range [low, high]. Which approach guarantees the most efficient traversal by leveraging the BST properties?

easy

A. Traverse all nodes in the tree and sum those within the range, ignoring BST properties.

B. Perform a depth-first search with pruning: skip left subtree if node value is less than low, skip right subtree if node value is greater than high.

C. Use dynamic programming to store sums of subtrees and combine results for the range query.

D. Apply a breadth-first search (BFS) to visit nodes level by level and sum values within the range.

Solution

1. Step 1: Understand BST property for pruning

   In a BST, left subtree nodes are smaller and right subtree nodes are larger than the current node. This allows skipping entire subtrees outside the range.

2. Step 2: Choose DFS with pruning

   DFS with pruning visits only nodes that could fall within [low, high], avoiding unnecessary traversal and improving efficiency.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Pruning reduces nodes visited compared to full traversal [OK]

Hint: BST pruning skips irrelevant subtrees [OK]

Common Mistakes:

• Ignoring BST properties leads to full traversal
• Using BFS misses pruning advantage

2. Examine the following code snippet intended to balance a BST by collecting nodes via inorder traversal and rebuilding the tree. Identify the subtle bug that could cause incorrect tree structure or cycles.

medium

A. The left and right pointers of nodes are not reset before rebuilding.

B. The inorder traversal appends nodes instead of values.

C. The middle index calculation uses integer division which may skew balance.

D. The stack is popped instead of dequeued, reversing processing order.

Solution

1. Step 1: Identify pointer reset necessity

   When rebuilding, left and right pointers must be reset to avoid old links causing cycles.

2. Step 2: Locate missing reset in code

   Commented out line resetting node.left and node.right causes bug.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Not resetting pointers -> cycles or incorrect tree [OK]

Hint: Always reset node pointers when rebuilding trees [OK]

Common Mistakes:

• Ignoring pointer reset leads to subtle bugs
• Misunderstanding traversal appending nodes is correct
• Thinking stack order affects correctness here

3. What is the time complexity of the optimal iterative pruning algorithm for trimming a BST with n nodes, and why?

medium

A. O(log n), because pruning skips entire subtrees quickly.

B. O(n^2), because nested loops may cause repeated visits to nodes.

C. O(n log n), because each pruning step may traverse log n nodes repeatedly.

D. O(n), because each node is visited at most once during pruning.

Solution

1. Step 1: Analyze root adjustment loop

   Root moves down skipping invalid nodes, each step moves to a child, total O(n) in worst case.

2. Step 2: Analyze left and right subtree trimming loops

   Each inner loop removes invalid children by pointer reassignment, each node visited once overall.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Each node processed once, total O(n) time [OK]

Hint: Each node visited once despite nested loops [OK]

Common Mistakes:

• Assuming pruning is O(log n) due to BST
• Confusing nested loops as O(n^2)

4. Suppose you want to extend the BST Iterator to support repeated calls to next() that return the same element multiple times (i.e., allow reuse of elements). Which modification to the Morris traversal based iterator is correct?

hard

A. Remove thread restoration to keep the tree threaded and allow repeated visits to the same node.

B. Store all elements in a list during initialization to allow repeated next() calls without traversal.

C. Modify _advance() to not move current pointer after returning next_val, so next() returns same value again.

D. Use a stack-based iterator and push nodes multiple times to simulate repeated next() calls.

Solution

1. Step 1: Understand reuse requirement

   Allowing repeated next() calls to return the same element requires storing elements since Morris traversal advances and loses previous state.

2. Step 2: Evaluate modifications

   Removing thread restoration (A) corrupts tree, modifying _advance() to not move current (C) breaks traversal logic, and pushing nodes multiple times on stack (B) is inefficient and incorrect. Storing all elements upfront (D) enables repeated next() calls reliably.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Pre-storing elements supports repeated next() calls without traversal [OK]

Hint: Reuse requires storing elements, not traversal tricks [OK]

Common Mistakes:

• Assuming traversal can be paused and repeated
• Ignoring tree corruption from missing restoration
• Trying to simulate reuse with threads

5. Suppose the BST can contain duplicate values, and you want to find all nodes with a given value. Which modification to the optimal iterative search algorithm correctly finds all such nodes?

hard

A. Stop at the first found node and return it, since duplicates are not allowed in BSTs.

B. Modify the search to continue searching both left and right subtrees even after finding a matching node.

C. Traverse the entire tree recursively to collect all nodes with the target value, ignoring BST property.

D. Use a queue to perform BFS and collect all nodes with the target value efficiently.

Solution

1. Step 1: Understand duplicates in BST

   Duplicates can appear on either left or right subtree depending on BST definition.

2. Step 2: Modify search to find all matches

   After finding a node with val, continue searching both subtrees to find all duplicates.

3. Step 3: Avoid full traversal

   Using BST property to prune search still possible by checking subtrees where duplicates may exist.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Continuing search after first match finds all duplicates [OK]

Hint: Duplicates require searching both subtrees after match [OK]

Common Mistakes:

• Stopping at first match or ignoring BST property completely