LeetCode 653: Two Sum IV - Input is a BST Solution in Python – A Step-by-Step Guide

What Is LeetCode 653: Two Sum IV - Input is a BST?

In LeetCode 653: Two Sum IV - Input is a BST, you’re given the root of a binary search tree (BST) and an integer k. Your task is to determine if there exist two nodes in the tree whose values sum to k, returning True if so, False otherwise. A BST ensures that for any node, all values in the left subtree are less than the node’s value, and all in the right subtree are greater. For example, with a tree [5, 3, 6, 2, 4, null, 7] and k = 9, nodes 2 and 7 sum to 9, so you’d return True. This problem tests your ability to adapt the classic "Two Sum" problem to a BST structure.

Problem Statement

• Input:
• root: Root node of a BST.
• k: Integer (target sum).
• Output: A boolean—True if two nodes sum to k, False otherwise.
• Rules:
• BST: Left subtree < node < right subtree.
• Find two distinct nodes whose values sum to k.
• Return True if such a pair exists.

Constraints

• Number of nodes: 1 to 10⁴.
• -10⁴ ≤ Node.val ≤ 10⁴.
• root is a valid BST.
• -10⁵ ≤ k ≤ 10⁵.

Examples

• Input: root = [5, 3, 6, 2, 4, null, 7], k = 9
• Output: True (2 + 7 = 9)
• Input: root = [5, 3, 6, 2, 4, null, 7], k = 28
• Output: False (No pair sums to 28)
• Input: root = [2, 1], k = 3
• Output: True (1 + 2 = 3)

These examples set the tree—let’s solve it!

Understanding the Problem: Finding the Pair

To solve LeetCode 653: Two Sum IV - Input is a BST in Python, we need to find two distinct nodes in a BST whose values sum to k. A brute-force approach—checking all pairs—would be O(n²), inefficient for n ≤ 10⁴. Since it’s a BST, we can leverage its sorted nature (via inorder traversal) or search properties. We’ll use:

• Best Solution (Inorder Traversal with Hash Set): O(n) time, O(n) space—fast and simple.
• Alternative Solution (Two-Pointer with BST Iterators): O(n) time, O(h) space—BST-specific but complex (h = height).

Let’s start with the hash set solution, breaking it down for beginners.

Best Solution: Inorder Traversal with Hash Set

Why This Is the Best Solution

The inorder traversal with hash set approach is the top choice for LeetCode 653 because it’s efficient—O(n) time with O(n) space—and adapts the classic "Two Sum" hash set method to a BST by traversing all nodes once, using a set to track complements. It fits constraints (n ≤ 10⁴) perfectly and is easy to understand, even without deep BST knowledge. It’s like scanning the tree and checking your list for a match!

How It Works

Think of this as a sum checker:

• Step 1: Initialize Hash Set:
• Set to store visited node values.
• Step 2: Inorder Traversal:
• Traverse BST (left, root, right).
• For each node:
• Check if k - node.val is in set (complement exists).
• If yes, return True.
• Add node.val to set.
• Step 3: Return Result:
• If no pair found, return False.

It’s like a number matcher—traverse and find!

Step-by-Step Example

Example: root = [5, 3, 6, 2, 4, null, 7], k = 9

• Step 1: Init: seen = set().
• Step 2: Inorder (2, 3, 4, 5, 6, 7):
• Node 2: 9-2=7 not in set, add 2, seen = {2}.
• Node 3: 9-3=6 not in set, add 3, seen = {2, 3}.
• Node 4: 9-4=5 not in set, add 4, seen = {2, 3, 4}.
• Node 5: 9-5=4 in set, return True.
• Step 3: Found pair (4, 5), return True.
• Output: True.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

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

class Solution:
    def findTarget(self, root: TreeNode, k: int) -> bool:
        # Step 1: Initialize hash set
        seen = set()

        # Step 2: Helper for inorder traversal
        def inorder(node):
            if not node:
                return False

            # Check left subtree
            if inorder(node.left):
                return True

            # Check current node
            complement = k - node.val
            if complement in seen:
                return True
            seen.add(node.val)

            # Check right subtree
            return inorder(node.right)

        # Step 3: Start traversal
        return inorder(root)

• Lines 1-6: TreeNode class (standard).
• Line 10: Init: Empty set for seen values.
• Lines 13-27: inorder:
• Recurse left, check complement, add value, recurse right.
• Return True if pair found, False otherwise.
• Line 30: Start from root.
• Time Complexity: O(n)—visit each node once.
• Space Complexity: O(n)—hash set size.

This is like a sum spotter—traverse and match!

Alternative Solution: Two-Pointer with BST Iterators

Why an Alternative Approach?

The two-pointer with BST iterators approach uses BST properties—O(n) time, O(h) space (h = height). It’s more BST-specific, simulating a sorted array with two pointers via iterators, but complex due to iterator implementation. It’s like walking the tree from both ends to meet in the middle!

How It Works

Picture this as a tree walker:

• Step 1: Create BST iterators:
• Left iterator: Smallest values (inorder).
• Right iterator: Largest values (reverse inorder).
• Step 2: Two-pointer search:
• Start with smallest (left) and largest (right).
• If sum = k, return True.
• If sum < k, advance left; if sum > k, retreat right.
• Step 3: Return False if no pair found.

It’s like a pointer dance—step and sum!

Step-by-Step Example

Example: Same as above

• Step 1: Iterators:
• Left: 2, 3, 4, 5, 6, 7.
• Right: 7, 6, 5, 4, 3, 2.
• Step 2: Search:
• Left=2, Right=7: 2+7=9, return True.
• Step 3: Found pair, return True.
• Output: True.

Code for Two-Pointer Approach

Copy codeclass BSTIterator:
    def __init__(self, root: TreeNode, reverse: bool):
        self.stack = []
        self.reverse = reverse
        self._push(root)

    def _push(self, node):
        while node:
            self.stack.append(node)
            node = node.right if self.reverse else node.left

    def next(self) -> int:
        node = self.stack.pop()
        self._push(node.left if self.reverse else node.right)
        return node.val

    def hasNext(self) -> bool:
        return len(self.stack) > 0

class Solution:
    def findTarget(self, root: TreeNode, k: int) -> bool:
        # Step 1: Initialize iterators
        left_iter = BSTIterator(root, False)  # Smallest to largest
        right_iter = BSTIterator(root, True)  # Largest to smallest

        # Step 2: Two-pointer search
        left = left_iter.next()
        right = right_iter.next()
        while left < right:
            curr_sum = left + right
            if curr_sum == k:
                return True
            elif curr_sum < k:
                left = left_iter.next()
            else:
                right = right_iter.next()

        # Step 3: No pair found
        return False

• Lines 1-17: BSTIterator: Stack-based iterator for inorder (left) or reverse (right).
• Lines 21-35: Search:
• Use iterators to get smallest and largest, adjust pointers.
• Time Complexity: O(n)—traverse each node once.
• Space Complexity: O(h)—stack size (height).

It’s a BST dancer—iterate and sum!

Comparing the Two Solutions

• Hash Set (Best):
• Pros: O(n) time, O(n) space, simple and general.
• Cons: More space than height-based.
• Two-Pointer (Alternative):
• Pros: O(n) time, O(h) space, BST-specific.
• Cons: Iterator complexity.

Hash set wins for simplicity.

Additional Examples and Edge Cases

• Input: [1], k = 2
• Output: False.
• Input: [2, 1, 3], k = 4
• Output: True (1 + 3 = 4).

Both handle these well.

Complexity Breakdown

• Hash Set: Time O(n), Space O(n).
• Two-Pointer: Time O(n), Space O(h).

Hash set is optimal for ease.

Key Takeaways

• Hash Set: Traversal simplicity—smart!
• Two-Pointer: BST elegance—clear!
• Sums: Trees are fun.
• Python Tip: Sets rock—see Python Basics.

Final Thoughts: Find That Sum

LeetCode 653: Two Sum IV - Input is a BST in Python is a fun tree challenge. Inorder with hash set offers speed and clarity, while two-pointer with iterators leverages BST properties. Want more? Try LeetCode 1: Two Sum or LeetCode 98: Validate Binary Search Tree. Ready to sum? Head to Solve LeetCode 653 on LeetCode and find that pair today!