Pair Sum in BST

JavaView on GFG

Time: O(n)

Space: O(n)

Intuition

Find if BST contains a pair with given sum. Two-pointer using in-order (ascending) and reverse in-order (descending).

Algorithm

1Two stacks for in-order and reverse in-order iteration. Two-pointer approach: sum < target advance left, else advance right.

Common Pitfalls

•Same as LC 653. Can also convert to sorted array via in-order, then two-pointer. O(n) time O(h) space.

Pair Sum in BST.java

Java

// Approach: Augmented BST inorder + two pointers, or HashSet: traverse and check if (target - node.val) is in set.
// Time: O(n) Space: O(n)
class Node {
    int data;
    Node left, right;

    public Node(int d) {
        data = d;
        left = right = null;
    }
}

class Solution {
    HashSet<Integer> s = new HashSet<>();

    boolean findTarget(Node root, int target) {
        if (root == null)
            return false;
        boolean l = findTarget(root.left, target);
        boolean temp = false;
        if (s.contains(target - root.data))
            temp = true;
        s.add(root.data);
        boolean r = findTarget(root.right, target);
        return (l || r) || temp;
    }
}

Was this solution helpful?