1305. All Elements in Two Binary Search Trees LeetCode Solution

In this guide, you will get 1305. All Elements in Two Binary Search Trees LeetCode Solution with the best time and space complexity. The solution to All Elements in Two Binary Search Trees 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
All Elements in Two Binary Search Trees solution in C++
All Elements in Two Binary Search Trees solution in Java
All Elements in Two Binary Search Trees solution in Python
Additional Resources

1305. All Elements in Two Binary Search Trees LeetCode Solution image

Problem Statement of All Elements in Two Binary Search Trees

Given two binary search trees root1 and root2, return a list containing all the integers from both trees sorted in ascending order.

Example 1:

Input: root1 = [2,1,4], root2 = [1,0,3]
Output: [0,1,1,2,3,4]

Example 2:

Input: root1 = [1,null,8], root2 = [8,1]
Output: [1,1,8,8]

Constraints:

The number of nodes in each tree is in the range [0, 5000].
-105 <= Node.val <= 105

Complexity Analysis

Time Complexity:
Space Complexity:

1305. All Elements in Two Binary Search Trees LeetCode Solution in C++

class BSTIterator {
 public:
  BSTIterator(TreeNode* root) {
    pushLeftsUntilNull(root);
  }

  int peek() {
    return stack.top()->val;
  }

  void next() {
    TreeNode* node = stack.top();
    stack.pop();
    pushLeftsUntilNull(node->right);
  }

  bool hasNext() {
    return !stack.empty();
  }

 private:
  stack<TreeNode*> stack;

  void pushLeftsUntilNull(TreeNode* node) {
    while (node != nullptr) {
      stack.push(node);
      node = node->left;
    }
  }
};

class Solution {
 public:
  vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {
    vector<int> ans;
    BSTIterator bstIterator1(root1);
    BSTIterator bstIterator2(root2);

    while (bstIterator1.hasNext() && bstIterator2.hasNext())
      if (bstIterator1.peek() < bstIterator2.peek()) {
        ans.push_back(bstIterator1.peek());
        bstIterator1.next();
      } else {
        ans.push_back(bstIterator2.peek());
        bstIterator2.next();
      }

    while (bstIterator1.hasNext()) {
      ans.push_back(bstIterator1.peek());
      bstIterator1.next();
    }

    while (bstIterator2.hasNext()) {
      ans.push_back(bstIterator2.peek());
      bstIterator2.next();
    }

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

1305. All Elements in Two Binary Search Trees LeetCode Solution in Java

class BSTIterator {
  public BSTIterator(TreeNode root) {
    pushLeftsUntilNull(root);
  }

  public int peek() {
    return stack.peek().val;
  }

  public void next() {
    pushLeftsUntilNull(stack.pop().right);
  }

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

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

  private void pushLeftsUntilNull(TreeNode node) {
    while (node != null) {
      stack.push(node);
      node = node.left;
    }
  }
}

class Solution {
  public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
    List<Integer> ans = new ArrayList<>();
    BSTIterator bstIterator1 = new BSTIterator(root1);
    BSTIterator bstIterator2 = new BSTIterator(root2);

    while (bstIterator1.hasNext() && bstIterator2.hasNext())
      if (bstIterator1.peek() < bstIterator2.peek()) {
        ans.add(bstIterator1.peek());
        bstIterator1.next();
      } else {
        ans.add(bstIterator2.peek());
        bstIterator2.next();
      }

    while (bstIterator1.hasNext()) {
      ans.add(bstIterator1.peek());
      bstIterator1.next();
    }

    while (bstIterator2.hasNext()) {
      ans.add(bstIterator2.peek());
      bstIterator2.next();
    }

    return ans;
  }
}
// code provided by PROGIEZ