algoadvance

Leetcode 653. Two Sum IV

Problem Statement

Given the root of a Binary Search Tree (BST) and an integer k, return true if there exist two elements in the BST such that their sum is equal to k, otherwise return false.

Clarifying Questions

1. Input Constraints:
   • What will be the range of values for k?
   • What is the range of possible node values in the BST (e.g., can they be negative)?
   • Is it guaranteed that the tree will have at least one node?
2. BST Characteristics:
   • Can the BST contain duplicate values?
   • What is the maximum number of nodes the BST can have?
3. Output:
   • Should I return a boolean value as the output?

Example

Consider the below BST and k = 9:

    5
   / \
  3   6
 / \   \
2   4   7

Here, the sum of nodes 3 and 6 is 9, so the output should be true.

Strategy

1. In-Order Traversal: Utilize the in-order traversal to convert the BST into a sorted array.
2. Two-Pointer Technique: Use two pointers to check for the target sum k.

Code

import java.util.ArrayList;
import java.util.List;

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;
    }
}

public class Solution {
    // Function to find if there exist two elements in BST that sum up to k
    public boolean findTarget(TreeNode root, int k) {
        List<Integer> sortedList = new ArrayList<>();
        inOrderTraversal(root, sortedList);

        int left = 0, right = sortedList.size() - 1;
        while (left < right) {
            int sum = sortedList.get(left) + sortedList.get(right);
            if (sum == k) {
                return true;
            } else if (sum < k) {
                left++;
            } else {
                right--;
            }
        }
        return false;
    }

    // Helper function for in-order traversal to get sorted list
    private void inOrderTraversal(TreeNode root, List<Integer> sortedList) {
        if (root == null) {
            return;
        }
        inOrderTraversal(root.left, sortedList);
        sortedList.add(root.val);
        inOrderTraversal(root.right, sortedList);
    }
}

Time Complexity

• In-Order Traversal: O(N), where N is the number of nodes in the BST.
• Two-Pointer Search: O(N), where N is the number of nodes in the BST.
• Overall Complexity: O(N) for traversing and checking the sum.

Space Complexity

• Auxiliary Space for List: O(N), to store the nodes’ values.
• Recursion Call Stack: O(H), where H is the height of the BST and in the worst case is O(N).
• Overall Space Complexity: O(N).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?