LeetCode 653 Two Sum IV - Input is a BST - In Order Traversal (Easy, Java, O(n))

• LeetCode 653. Two Sum IV - Input is a BST

Approach

The problem requires us to find if there exist any two nodes in a Binary Search Tree (BST) that sum up to a given target value k.

The solution uses an inorder traversal approach combined with a hash set to keep track of visited node values. As we traverse each node, we check if its complement (k - node.val) exists in the set. If found, we return true immediately. Otherwise, we add the current node's value to the set and continue traversing.

Explanation

1. Hash Set Tracking: We maintain a set of values we've encountered during our traversal. For each node, we check if its complement (target - current value) exists in the set.
2. Inorder Traversal: We traverse the BST in an inorder fashion (left-root-right), though any traversal order would work since we're checking all nodes.
3. Early Termination: If at any point we find the complement of the current node's value in our set, we immediately return true, optimizing the solution by avoiding unnecessary further checks.

This approach efficiently solves the problem by leveraging the properties of hash sets for O(1) lookups and performing a single traversal of the BST.

Solution Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean findTarget(TreeNode root, int k) {
        Set<Integer> seen = new HashSet<>();
        return inorderTraversal(root, k, seen);
    }

    public boolean inorderTraversal(TreeNode node, int k, Set<Integer> seen) {
        // Base case: If we reach a null node, we can't find the target
        if (node == null) {
            return false;
        }
        // Check if the complement (k-node.val) is in the 'seen' set.
        // If so, we found it
        if (seen.contains(k - node.val)) {
            return true;
        }

        // Add the current node's value to the 'seen' set.
        seen.add(node.val);

        // Recursively explore the left and right subtrees.
        return inorderTraversal(node.left, k, seen) || inorderTraversal(node.right, k, seen);
    }
}

Complexity Analysis

• Time Complexity: O(N), where N is the number of nodes in the BST.

  • We visit each node exactly once during the traversal.
  • HashSet operations (contains and add) are O(1) on average.

• Space Complexity: O(N)

  • The space is primarily used by the hash set to store node values, which can grow up to N elements in the worst case (when no pair is found).
  • The recursion stack can also take up O(N) space in the worst case (for a skewed tree). For a balanced BST, this would be O(log N).