All Elements in Two Binary Search Trees

Description

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].

Solution(javascript)

const getAllElements = function (root1, root2) {
  const aux = (node, current = []) => {
    if (!node) {
      return current
    }
    aux(node.left, current)
    current.push(node.val)
    aux(node.right, current)
    return current
  }
  const sorted1 = aux(root1)
  const sorted2 = aux(root2)
  const merge = (arr1 = [], arr2 = []) => {
    const result = []
    let i; let j
    for (i = 0, j = 0; i < arr1.length && j < arr2.length;) {
      if (arr1[i] <= arr2[j]) {
        result.push(arr1[i])
        i++
      } else {
        result.push(arr2[j])
        j++
      }
    }
    if (i < arr1.length) {
      result.push(...arr1.splice(i))
    }
    if (j < arr2.length) {
      result.push(...arr2.splice(j))
    }
    return result
  }
  return merge(sorted1, sorted2)
}