653. Two Sum IV – Input is a BST LeetCode Solution

In this guide, you will get 653. Two Sum IV – Input is a BST LeetCode Solution with the best time and space complexity. The solution to Two Sum IV – Input is a BST problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Two Sum IV – Input is a BST solution in C++
Two Sum IV – Input is a BST solution in Java
Two Sum IV – Input is a BST solution in Python
Additional Resources

653. Two Sum IV - Input is a BST LeetCode Solution image

Problem Statement of Two Sum IV – Input is a BST

Given the root of a binary search tree and an integer k, return true if there exist two elements in the BST such that their sum is equal to k, or false otherwise.

Example 1:

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

Example 2:

Input: root = [5,3,6,2,4,null,7], k = 28
Output: false

Constraints:

The number of nodes in the tree is in the range [1, 104].
-104 <= Node.val <= 104
root is guaranteed to be a valid binary search tree.
-105 <= k <= 105

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(h) \to O(n)

653. Two Sum IV – Input is a BST LeetCode Solution in C++

class BSTIterator {
 public:
  BSTIterator(TreeNode* root, bool leftToRight) : leftToRight(leftToRight) {
    pushUntilNull(root);
  }

  int next() {
    TreeNode* root = stack.top();
    stack.pop();
    pushUntilNull(leftToRight ? root->right : root->left);
    return root->val;
  }

 private:
  stack<TreeNode*> stack;
  bool leftToRight;

  void pushUntilNull(TreeNode* root) {
    while (root != nullptr) {
      stack.push(root);
      root = leftToRight ? root->left : root->right;
    }
  }
};

class Solution {
 public:
  bool findTarget(TreeNode* root, int k) {
    if (root == nullptr)
      return false;

    BSTIterator left(root, true);
    BSTIterator right(root, false);

    for (int l = left.next(), r = right.next(); l < r;) {
      const int sum = l + r;
      if (sum == k)
        return true;
      if (sum < k)
        l = left.next();
      else
        r = right.next();
    }

    return false;
  }
};
/* code provided by PROGIEZ */

653. Two Sum IV – Input is a BST LeetCode Solution in Java

class BSTIterator {
  public BSTIterator(TreeNode root, boolean leftToRight) {
    this.leftToRight = leftToRight;
    pushLeftsUntilNull(root);
  }

  public int next() {
    TreeNode root = stack.pop();
    pushLeftsUntilNull(leftToRight ? root.right : root.left);
    return root.val;
  }

  public boolean hasNext() {
    return !stack.isEmpty();
  }

  private Deque<TreeNode> stack = new ArrayDeque<>();
  private boolean leftToRight;

  private void pushLeftsUntilNull(TreeNode root) {
    while (root != null) {
      stack.push(root);
      root = leftToRight ? root.left : root.right;
    }
  }
}

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

    BSTIterator left = new BSTIterator(root, true);
    BSTIterator right = new BSTIterator(root, false);

    for (int l = left.next(), r = right.next(); l < r;) {
      final int sum = l + r;
      if (sum == k)
        return true;
      if (sum < k)
        l = left.next();
      else
        r = right.next();
    }

    return false;
  }
}
// code provided by PROGIEZ

653. Two Sum IV – Input is a BST LeetCode Solution in Python

class BSTIterator:
  def __init__(self, root: TreeNode | None, leftToRight: bool):
    self.stack = []
    self.leftToRight = leftToRight
    self._pushUntilNone(root)

  def next(self) -> int:
    node = self.stack.pop()
    if self.leftToRight:
      self._pushUntilNone(node.right)
    else:
      self._pushUntilNone(node.left)
    return node.val

  def _pushUntilNone(self, root: TreeNode | None):
    while root:
      self.stack.append(root)
      root = root.left if self.leftToRight else root.right


class Solution:
  def findTarget(self, root: TreeNode | None, k: int) -> bool:
    if not root:
      return False

    left = BSTIterator(root, True)
    right = BSTIterator(root, False)

    l = left.next()
    r = right.next()
    while l < r:
      summ = l + r
      if summ == k:
        return True
      if summ < k:
        l = left.next()
      else:
        r = right.next()

    return False
 # code by PROGIEZ