Two sum in BST

Intuition

An inorder traversal of a Binary Search Tree (BST) results in a sorted list of elements. This sorted nature can be utilized to find a pair of elements that add up to a specified sum (K). By applying the Two Sum technique to this sorted list, the solution becomes straightforward. Two pointers are set at the beginning and the end of the list. Their positions are adjusted based on whether their combined value is less than, greater than, or equal to the target sum.

Approach

Execute an inorder traversal of the BST to generate a sorted list of elements. This traversal follows the pattern: left subtree -> root -> right subtree.
With the sorted list in hand, set one pointer at the start (left end) and another at the end (right end) of the list.
Adjust the pointers as follows:
- If the sum of the values at the pointers is less than the target, move the left pointer to the right (towards larger values).
- If the sum is greater than the target, move the right pointer to the left (towards smaller values).
- If the sum equals the target, return the pair of values.

Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;

/**
 * Definition for a binary tree node.
 */
struct TreeNode {
    int data;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    bool twoSumBST(TreeNode* root, int k) {
        // Get sorted list of elements from BST
        vector<int> sorted_elements = inorderTraversal(root);

        // Initialize two pointers
        int left = 0, right = sorted_elements.size() - 1;

        // Use two pointers to find if there is a pair with sum k
        while (left < right) {
            int current_sum = sorted_elements[left] + sorted_elements[right];
            if (current_sum == k) {
                return true;
            } else if (current_sum < k) {
                left++;
            } else {
                right--;
            }
        }

        return false;
    }

private:
    // Helper function to perform inorder traversal and get sorted elements
    vector<int> inorderTraversal(TreeNode* node) {
        vector<int> elements;
        inorderHelper(node, elements);
        return elements;
    }

    // Recursive helper to fill elements during inorder traversal
    void inorderHelper(TreeNode* node, vector<int>& elements) {
        if (!node) return;
        inorderHelper(node->left, elements);
        elements.push_back(node->data);
        inorderHelper(node->right, elements);
    }
};

// Main method to test the solution
int main() {
    // Example tree: [5, 3, 6, 2, 4, nullptr, 7]
    TreeNode* root = new TreeNode(5);
    root->left = new TreeNode(3);
    root->right = new TreeNode(6);
    root->left->left = new TreeNode(2);
    root->left->right = new TreeNode(4);
    root->right->right = new TreeNode(7);

    int k = 9;
    Solution solution;
    bool result = solution.twoSumBST(root, k);
    cout << (result ? "True" : "False") << endl;  // Output: True

    // Clean up memory
    delete root->right->right;
    delete root->left->right;
    delete root->left->left;
    delete root->right;
    delete root->left;
    delete root;

    return 0;
}
import java.util.*;

class TreeNode {
    int data;
    TreeNode left;
    TreeNode right;
    
    // Constructor to create a TreeNode
    TreeNode(int val) {
        data = val;
        left = null;
        right = null;
    }
}

class Solution {
    
    // Function to check if there are two nodes in the BST whose sum equals k
    public boolean twoSumBST(TreeNode root, int k) {
        // Get sorted list of elements from BST
        List < Integer > sorted_elements = inorderTraversal(root);
        
        // Initialize two pointers
        int left = 0, right = sorted_elements.size() - 1;

        // Use two pointers to find if there is a pair with sum k
        while (left < right) {
            int current_sum = sorted_elements.get(left) + sorted_elements.get(right);
            if (current_sum == k) {
                return true;
            } else if (current_sum < k) {
                left++;
            } else {
                right--;
            }
        }

        return false;
    }

    // Helper function to perform inorder traversal and get sorted elements
    private List < Integer > inorderTraversal(TreeNode node) {
        List < Integer > elements = new ArrayList < > ();
        inorderHelper(node, elements);
        return elements;
    }

    // Recursive helper to fill elements during inorder traversal
    private void inorderHelper(TreeNode node, List < Integer > elements) {
        if (node == null) return;
        inorderHelper(node.left, elements);
        elements.add(node.data);
        inorderHelper(node.right, elements);
    }

    // Main method to test the solution
    public static void main(String[] args) {
        Solution solution = new Solution();
        
        // Creating a simple BST for testing
        TreeNode root = new TreeNode(20);
        root.left = new TreeNode(10);
        root.right = new TreeNode(30);
        root.left.left = new TreeNode(5);
        root.left.right = new TreeNode(15);
        root.right.left = new TreeNode(25);
        root.right.right = new TreeNode(35);
        
        int k = 30;
        boolean result = solution.twoSumBST(root, k);
        
        // Output the result
        System.out.println(result); // It should print true if two numbers sum to 30, otherwise false.
    }
}

# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.data = val
        self.left = left
        self.right = right

class Solution:
    def twoSumBST(self, root, k):
        # Helper function to perform inorder traversal and get sorted elements
        def inorder(node):
            if not node:
                return []
            return inorder(node.left) + [node.data] + inorder(node.right)
        
        # Get sorted list of elements from BST
        sorted_elements = inorder(root)
        
        # Initialize two pointers
        left, right = 0, len(sorted_elements) - 1
        
        # Use two pointers to find if there is a pair with sum k
        while left < right:
            current_sum = sorted_elements[left] + sorted_elements[right]
            if current_sum == k:
                return True
            elif current_sum < k:
                left += 1
            else:
                right -= 1
                
        return False

# Main method to test the solution
if __name__ == "__main__":
    # Example tree: [5, 3, 6, 2, 4, None, 7]
    root = TreeNode(5)
    root.left = TreeNode(3)
    root.right = TreeNode(6)
    root.left.left = TreeNode(2)
    root.left.right = TreeNode(4)
    root.right.right = TreeNode(7)
    
    k = 9
    solution = Solution()
    result = solution.twoSumBST(root, k)
    print(result)  # Output: True
class TreeNode {
    constructor(val = 0, left = null, right = null) {
        this.data = val;   
        this.left = left;
        this.right = right; 
    }
}

class Solution {

    twoSumBST(root, k) {
        // Edge case: if the tree is empty
        if (root === null) return false;

        // Helper function to perform inorder traversal and get sorted elements
        const inorderTraversal = (node) => {
            let elements = [];
            const inorderHelper = (node) => {
                if (node === null) return;
                inorderHelper(node.left);
                elements.push(node.data); 
                inorderHelper(node.right);
            };
            inorderHelper(node);
            return elements;
        };

        // Get sorted list of elements from BST
        const sortedElements = inorderTraversal(root);

        // Edge case: if there are fewer than 2 nodes
        if (sortedElements.length < 2) return false;

        // Initialize two pointers
        let left = 0, right = sortedElements.length - 1;

        // Use two pointers to find if there is a pair with sum k
        while (left < right) {
            const currentSum = sortedElements[left] + sortedElements[right];
            if (currentSum === k) {
                return true; 
            } else if (currentSum < k) {
                left++; 
            } else {
                right--; 
            }
        }

        return false; 
    }
}

// Example usage
const root = new TreeNode(5); // Create the root node with value 5
root.left = new TreeNode(3); // Left child of root with value 3
root.right = new TreeNode(6); // Right child of root with value 6
root.left.left = new TreeNode(2); // Left child of node 3 with value 2
root.left.right = new TreeNode(4); // Right child of node 3 with value 4
root.right.right = new TreeNode(7); // Right child of node 6 with value 7

const k = 9; // Target sum
const solution = new Solution();
const result = solution.twoSumBST(root, k);
console.log(result);  // Output: true

Complexity Analysis

Time Complexity: O(N), The time complexity is linear because we are traversing the entire binary search tree once to get the sorted elements, and then we are using two pointers to find the pair that sums to k, which also takes linear time.

Space Complexity: O(N), The space complexity is linear because we are storing the sorted elements in an array, which takes linear space.

Intuition

While a previous method used O(N) space complexity by storing the inorder traversal, this can be avoided by directly utilizing the properties of a Binary Search Tree (BST). Understanding the BST Iterator is crucial for this approach. The BSTIterator class provides functionality to access the next and previous elements in the BST. By initializing pointers 'i' and 'j' to the first and last elements of the inorder traversal using this class, the pointers can be moved through the tree using next() for larger values and before() for smaller values. This method efficiently navigates the BST to find the pair of elements that sum to the target value without needing additional storage for the traversal.

Approach

Initialize pointers 'i' and 'j' to the first and last elements of the BST's inorder traversal using the BSTIterator class.
Use the next() function to move pointer 'i' to larger values and the before() function to move pointer 'j' to smaller values within the BST.
Adjust the pointers based on their sum:
- If the sum of the values at the pointers is less than the target, increment pointer 'i' to move towards larger values.
- If the sum is greater than the target, decrement pointer 'j' to move towards smaller values.
- If the sum equals the target, return true.

Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int data;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};

// BST Iterator to iterate in the inorder and reverse inorder manner
class BSTIterator {
    stack<TreeNode*> st;
    bool reverse;
    
    // Helper function to push all left or right nodes
    void pushAll(TreeNode* node) {
        while (node != nullptr) {
            st.push(node);
            node = (reverse) ? node->right : node->left;
        }
    }
    
public:
    BSTIterator(TreeNode* root, bool isReverse) : reverse(isReverse) {
        pushAll(root);
    }
    
    // Check if there are more elements in the BST
    bool hasNext() {
        return !st.empty();
    }
    
    // Get the next element in the inorder or reverse inorder traversal
    int next() {
        TreeNode* node = st.top();
        st.pop();
        if (!reverse) pushAll(node->right);
        else pushAll(node->left);
        return node->data;
    }
};

class Solution {
public:
    bool twoSumBST(TreeNode* root, int k) {
        if (!root) return false;
        
        // Initialize two iterators
        BSTIterator l(root, false); // normal inorder
        BSTIterator r(root, true);  // reverse inorder
        
        int i = l.next();
        int j = r.next();
        
        while (i < j) {
            if (i + j == k) return true;
            else if (i + j < k) i = l.next();
            else j = r.next();
        }
        return false;
    }
};

int main() {
    // Create the tree
    TreeNode* root = new TreeNode(5);
    root->left = new TreeNode(3);
    root->right = new TreeNode(6);
    root->left->left = new TreeNode(2);
    root->left->right = new TreeNode(4);
    root->right->right = new TreeNode(7);

    // Create solution instance
    Solution solution;
    int k = 9;
    
    // Check if there exist two elements in the BST such that their sum is equal to k
    bool result = solution.twoSumBST(root, k);
    cout << (result ? "True" : "False") << endl;
    return 0;
}
import java.util.Stack;

// Definition for a binary tree node.
class TreeNode {
    int data;
    TreeNode left, right;
    TreeNode(int val) {
        data = val;
        left = null;
        right = null;
    }
}

// BST Iterator to iterate in the inorder and reverse inorder manner
class BSTIterator {
    private Stack<TreeNode> stack;
    private boolean reverse;

    // Constructor to initialize the iterator
    public BSTIterator(TreeNode root, boolean isReverse) {
        stack = new Stack<>();
        reverse = isReverse;
        pushAll(root);
    }

    // Helper function to push all left or right nodes
    private void pushAll(TreeNode node) {
        while (node != null) {
            stack.push(node);
            node = (reverse) ? node.right : node.left;
        }
    }

    // Check if there are more elements in the BST
    public boolean hasNext() {
        return !stack.isEmpty();
    }

    // Get the next element in the inorder or reverse inorder traversal
    public int next() {
        TreeNode node = stack.pop();
        if (!reverse) pushAll(node.right);
        else pushAll(node.left);
        return node.data;
    }
}

class Solution {
    public boolean twoSumBST(TreeNode root, int k) {
        if (root == null) return false;

        // Initialize two iterators
        BSTIterator l = new BSTIterator(root, false); // normal inorder
        BSTIterator r = new BSTIterator(root, true);  // reverse inorder

        int i = l.next();
        int j = r.next();

        while (i < j) {
            if (i + j == k) return true;
            else if (i + j < k) i = l.next();
            else j = r.next();
        }
        return false;
    }

    public static void main(String[] args) {
        // Create the tree
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(3);
        root.right = new TreeNode(6);
        root.left.left = new TreeNode(2);
        root.left.right = new TreeNode(4);
        root.right.right = new TreeNode(7);

        // Create solution instance
        Solution solution = new Solution();
        int k = 9;
        
        // Check if there exist two elements in the BST such that their sum is equal to k
        boolean result = solution.twoSumBST(root, k);
        System.out.println(result ? "True" : "False");
    }
}
# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.data = val
        self.left = left
        self.right = right

# BST Iterator to iterate in the inorder and reverse inorder manner
class BSTIterator:
    def __init__(self, root, is_reverse):
        self.stack = []
        self.reverse = is_reverse
        self.pushAll(root)
    
    # Helper function to push all left or right nodes
    def pushAll(self, node):
        while node:
            self.stack.append(node)
            node = node.right if self.reverse else node.left
    
    # Check if there are more elements in the BST
    def hasNext(self):
        return len(self.stack) > 0
    
    # Get the next element in the inorder or reverse inorder traversal
    def next(self):
        node = self.stack.pop()
        if not self.reverse:
            self.pushAll(node.right)
        else:
            self.pushAll(node.left)
        return node.data

class Solution:
    def twoSumBST(self, root, k):
        if not root:
            return False

        # Initialize two iterators
        left_iter = BSTIterator(root, False)  # normal inorder
        right_iter = BSTIterator(root, True)  # reverse inorder

        i = left_iter.next()
        j = right_iter.next()

        while i < j:
            if i + j == k:
                return True
            elif i + j < k:
                i = left_iter.next()
            else:
                j = right_iter.next()
        
        return False

def main():
    # Create the tree
    root = TreeNode(5)
    root.left = TreeNode(3)
    root.right = TreeNode(6)
    root.left.left = TreeNode(2)
    root.left.right = TreeNode(4)
    root.right.right = TreeNode(7)

    # Create solution instance
    solution = Solution()
    k = 9
    
    # Check if there exist two elements in the BST such that their sum is equal to k
    result = solution.twoSumBST(root, k)
    print("True" if result else "False")

if __name__ == "__main__":
    main()
// Definition for a binary tree node.
class TreeNode {
    constructor(val = 0, left = null, right = null) {
        this.data = val;
        this.left = left;
        this.right = right;
    }
}

// BST Iterator to iterate in the inorder and reverse inorder manner
class BSTIterator {
    constructor(root, isReverse) {
        this.stack = [];
        this.reverse = isReverse;
        this.pushAll(root);
    }

    // Helper function to push all left or right nodes
    pushAll(node) {
        while (node !== null) {
            this.stack.push(node);
            node = this.reverse ? node.right : node.left;
        }
    }

    // Check if there are more elements in the BST
    hasNext() {
        return this.stack.length > 0;
    }

    // Get the next element in the inorder or reverse inorder traversal
    next() {
        const node = this.stack.pop();
        if (!this.reverse) this.pushAll(node.right);
        else this.pushAll(node.left);
        return node.data;
    }
}

class Solution {
    twoSumBST(root, k) {
        if (!root) return false;

        // Initialize two iterators
        const leftIter = new BSTIterator(root, false); // normal inorder
        const rightIter = new BSTIterator(root, true); // reverse inorder

        let i = leftIter.next();
        let j = rightIter.next();

        while (i < j) {
            if (i + j === k) return true;
            else if (i + j < k) i = leftIter.next();
            else j = rightIter.next();
        }
        return false;
    }
}

// Example usage:
const main = () => {
    // Create the tree
    const root = new TreeNode(5);
    root.left = new TreeNode(3);
    root.right = new TreeNode(6);
    root.left.left = new TreeNode(2);
    root.left.right = new TreeNode(4);
    root.right.right = new TreeNode(7);

    // Create solution instance
    const solution = new Solution();
    const k = 9;

    // Check if there exist two elements in the BST such that their sum is equal to k
    const result = solution.twoSumBST(root, k);
    console.log(result ? "True" : "False");
};

main();

Complexity Analysis

Time Complexity: O(N), the code iterates over the BST once to initialize the iterators, and then iterates over the BST again to find the two sum, where N is the number of nodes in the BST.

Space Complexity: O(N), the code uses two iterators, each of which stores at most N nodes in the stack, to iterate over the BST.

Problem List

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition

Approach

Dry Run

Solution

Complexity Analysis

Intuition

Approach

Dry Run

Solution

Complexity Analysis

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code

Facts