All Elements in Two Binary Search Trees
LeetCode September - Day 5
Problem Statement
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 = [0,-10,10], root2 = [5,1,7,0,2]
Output: [-10,0,0,1,2,5,7,10]
Example 3:
Input: root1 = [], root2 = [5,1,7,0,2]
Output: [0,1,2,5,7]
Example 4:
Input: root1 = [0,-10,10], root2 = []
Output: [-10,0,10]
Example 5:

Input: root1 = [1,null,8], root2 = [8,1]
Output: [1,1,8,8]
Constraints:
- Each tree has at most 5000 nodes.
- Each node’s value is between [$-10^5$, $10^5$].
Inputs, Outputs, Constraints & Exceptions
- I: - TreeNode {root1}
- TreeNode {root2}
- O: number[]
- C: none other than the above
- E: - root1 or root2 is null
- root1 or root2 only have one node
Code
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root1
* @param {TreeNode} root2
* @return {number[]}
*/
function getAllElements(root1, root2) {
const M = inOrder(root1, [])
const N = inOrder(root2, [])
return merge(M, N)
};
function inOrder(node, res){
if(node !== null) {
if(node.left) inOrder(node.left, res);
res.push(node.val);
if(node.right) inOrder(node.right, res);
}
return res
}
function merge(M, N) {
let [i, j, k] = [0, 0, 0]
let res = []
while(i < M.length && j < N.length){
if(M[i] < N[j]) {
res.push(M[i++])
} else if (M[i] > N[j]){
res.push(N[j++])
} else {
res.push(N[j++], M[i++])
}
}
if(i < M.length){
res = [...res, ...M.slice(i)]
}
if(j < N.length){
res = [...res, ...N.slice(j)]
}
return res
}
Time complexity: O(M + N)
- where M is the number of nodes in root1
- and N is the number of nodes in root2
Space complexity: O(M + N)