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. Consider the following Python code snippet for balancing a BST using inorder traversal and iterative construction. Given the BST with nodes 1, 2, 3 inserted in that order, what is the value of the root node after balancing?

easy

A. 1

B. 2

C. 3

D. None (empty tree)

Solution

1. Step 1: Perform inorder traversal on BST with nodes 1, 2, 3

   Inorder traversal yields nodes in sorted order: [1, 2, 3].

2. Step 2: Iteratively build balanced BST choosing middle node

   Middle index is 1 (0-based), so node with value 2 becomes root.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Middle of [1,2,3] is 2 -> root value 2 [OK]

Hint: Middle element of sorted nodes becomes root [OK]

Common Mistakes:

• Choosing left or right middle always, skewing tree
• Confusing preorder with inorder traversal results
• Forgetting to reset left/right pointers causing cycles

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

3. What is the time complexity of the optimal divide-and-conquer approach to convert a sorted array of length n into a height-balanced BST, and why?

medium

A. O(n log n), because each recursive call processes half the array and builds subtrees.

B. O(n), because each element is visited exactly once to create nodes without extra overhead.

C. O(n^2), because the recursion tree has n levels and each level processes n elements.

D. O(log n), because the tree height is log n and only root nodes are created at each level.

Solution

1. Step 1: Analyze recursion calls

   The algorithm visits each element exactly once to create a TreeNode, splitting the array into halves recursively.

2. Step 2: Calculate total work

   Each element is processed once, so total time is proportional to n.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Single pass over array with divide-and-conquer -> O(n) time [OK]

Hint: Each element processed once -> O(n) time [OK]

Common Mistakes:

• Confusing recursion depth with total work
• Assuming O(n log n) due to recursion

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

5. Suppose the BST validation problem is modified so that duplicate values are allowed only on the right subtree (i.e., node values in the right subtree can be equal to the current node). Which modification to the inorder traversal check correctly validates this variant?

hard

A. Change the comparison to node.val < prev[0] to allow duplicates on the right subtree.

B. Change the comparison to node.val < prev[0] for all nodes except when node is right child, then allow node.val == prev[0].

C. Change the comparison to node.val <= prev[0] to allow duplicates anywhere.

D. Change the comparison to node.val < prev[0] only when traversing left subtree, and node.val <= prev[0] when traversing right subtree.

Solution

1. Step 1: Understand variant allowing duplicates only on right subtree

   Duplicates allowed only if they appear in right subtree, so inorder sequence can have equal values only when moving right.

2. Step 2: Modify comparison accordingly

   During inorder traversal, allow node.val == prev[0] only if current node is right child of previous node; otherwise, enforce strict inequality.

3. Step 3: Reason why other options fail

   Change the comparison to node.val < prev[0] to allow duplicates on the right subtree. allows duplicates anywhere; Change the comparison to node.val <= prev[0] to allow duplicates anywhere. allows duplicates anywhere; Change the comparison to node.val < prev[0] only when traversing left subtree, and node.val <= prev[0] when traversing right subtree. is ambiguous and not implementable in simple inorder traversal without parent info.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Allow duplicates only on right subtree requires conditional equality check [OK]

Hint: Duplicates allowed only on right subtree require conditional comparison [OK]

Common Mistakes:

• Allowing duplicates anywhere
• Ignoring subtree direction in comparison
• Using simple <= everywhere