Two Sum IV - Input is a BST

Easy Trees & BST Miscellaneous BST Questions Original on LeetCode

Two Sum IV - Input is a BST is a easy trees & bst problem solved with the miscellaneous bst questions pattern. The best approach, two bst iterators (o(h) space), runs in O(n) time and O(h) space. Below are 2 approaches in Java, from hash set during dfs up.

Problem

Given the root of a BST and an integer k, return whether there are two different nodes whose values add up to k.

Examples

Example 1

Input: root = [5, 3, 6, 2, 4, null, 7], k = 9
Output: true
Why: 2 + 7, or 3 + 6, or 4 + 5.

Example 2

Input: same tree, k = 28
Output: false

Constraints

The tree has 1 to 10^4 nodes.
The two values must come from different nodes.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Code

Code appears here once we start writing it.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

Approach	Time	Space
Hash set during DFS	`O(n)`	`O(n)`
Two BST iterators (O(h) space)	`O(n)`	`O(h)`

1Hash set during DFS

TimeO(n)

SpaceO(n)

Traverse the tree; for each value, check whether k - value was already seen.

DFS; if seen contains k - val return true; add val.

Java

class Solution {
    public boolean findTarget(TreeNode root, int k) {
        return dfs(root, k, new HashSet<>());
    }

    private boolean dfs(TreeNode n, int k, Set<Integer> seen) {
        if (n == null) return false;
        if (seen.contains(k - n.val)) return true;
        seen.add(n.val);
        return dfs(n.left, k, seen) || dfs(n.right, k, seen);
    }
}

2Two BST iterators (O(h) space)

TimeO(n)

SpaceO(h)

Run two iterative inorder traversals at once: one ascending from the smallest value and one descending from the largest. They act as the left and right pointers of Two Sum II without building a list.

Left stack: push the left spine. Right stack: push the right spine.
sum = left top + right top. Equal: true. Smaller: advance the left iterator. Larger: advance the right iterator.
Stop when the two iterators meet.

Java

class Solution {
    public boolean findTarget(TreeNode root, int k) {
        Deque<TreeNode> lo = new ArrayDeque<>(), hi = new ArrayDeque<>();
        for (TreeNode n = root; n != null; n = n.left) lo.push(n);
        for (TreeNode n = root; n != null; n = n.right) hi.push(n);
        while (!lo.isEmpty() && !hi.isEmpty() && lo.peek() != hi.peek()) {
            int sum = lo.peek().val + hi.peek().val;
            if (sum == k) return true;
            if (sum < k) {
                TreeNode n = lo.pop();
                for (n = n.right; n != null; n = n.left) lo.push(n);
            } else {
                TreeNode n = hi.pop();
                for (n = n.left; n != null; n = n.right) hi.push(n);
            }
        }
        return false;
    }
}

Edge cases to test

k = 2 · (some value): the same node cannot be used twice
Single node

Hints

Hint 1

An inorder list of a BST is sorted, so Two Sum II's two pointers apply.

FAQ

What is the best time complexity for Two Sum IV - Input is a BST?

Two BST iterators (O(h) space) runs in O(n) time and O(h) extra space.

Which pattern does Two Sum IV - Input is a BST use?

It is a trees & bst problem that uses the miscellaneous bst questions pattern. Other problems with the same pattern: Inorder Successor in BST, Inorder predecessor, Floor in BST.

Is there a brute force solution for Two Sum IV - Input is a BST?

Yes. Hash set during DFS takes O(n) time and O(n) space. Traverse the tree; for each value, check whether k - value was already seen.

Which edge cases should I test for Two Sum IV - Input is a BST?

k = 2 · (some value): the same node cannot be used twice; Single node.