All Elements in Two Binary Search Trees – Leetcode Solution

In this post, we are going to solve the 1305. All Elements in Two Binary Search Trees problem of Leetcode. This problem 1305. All Elements in Two Binary Search Trees is a Leetcode medium level problem. Let’s see the code, 1305. All Elements in Two Binary Search Trees – Leetcode Solution.

Problem

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

Now, let’s see the code of 1305. All Elements in Two Binary Search Trees – Leetcode Solution.

All Elements in Two Binary Search Trees – Leetcode Solution

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

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
        List<Integer> list1 = new ArrayList<Integer>();
        List<Integer> list2 = new ArrayList<Integer>();
        List<Integer> ans = new ArrayList<Integer>();
        
        inorder(root1,list1);
        inorder(root2,list2);
        
        int i=0,j=0;
        
        while(i<list1.size() && j<list2.size()){
            if(list1.get(i) < list2.get(j)){
                ans.add(list1.get(i));
                i++;
            }
            else{
                 ans.add(list2.get(j));
                j++;
            }
        }
        
        while(i<list1.size()){
            ans.add(list1.get(i));
            i++;
        }
         while(j<list2.size()){
            ans.add(list2.get(j));
            j++;
        }
        
        return ans;
        
    }
    
    public void inorder(TreeNode root, List<Integer> list){
        if(root == null)return;
        inorder(root.left,list);
        list.add(root.val);
        inorder(root.right,list);
    }
}

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

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {
        stack<TreeNode *> st1, st2;
        vector<int> res;
        
        while(root1 || root2 || !st1.empty() || !st2.empty()){
            while(root1){
                st1.push(root1);
                root1 = root1->left;
            }
            while(root2){
                st2.push(root2);
                root2 = root2->left;
            }
            if(st2.empty() || (!st1.empty() && st1.top()->val <= st2.top()->val)){
                root1 = st1.top();
                st1.pop();
                res.push_back(root1->val);
                root1 = root1->right;
            }
            else{
                root2 = st2.top();
                st2.pop();
                res.push_back(root2->val);
                root2 = root2->right;
            }
        }
        return res;
    }
};

1305. All Elements in Two Binary Search Trees– Solution in Python

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def getAllElements(self, root1, root2):
        def inorder(root, lst):
            if not root: return
            inorder(root.left, lst)
            lst.append(root.val)
            inorder(root.right, lst)
        
        lst1, lst2 = [], []
        inorder(root1, lst1)
        inorder(root2, lst2)
        
        i1, i2, res = 0, 0, []
        s1, s2 = len(lst1), len(lst2)
        
        while i1 < s1 and i2 < s2:
            if lst1[i1] < lst2[i2]:
                res += [lst1[i1]]
                i1 += 1
            else:
                res += [lst2[i2]]
                i2 += 1
                
        return res + lst1[i1:] + lst2[i2:]
        

Note: This problem 1305. All Elements in Two Binary Search Trees is generated by Leetcode but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.

Leave a Comment

Your email address will not be published.