1305. All Elements in Two Binary Search Trees

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

Problem Summary

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

Notes:

• Each tree has at most 5000 nodes.
• Each node's value is between [-10^5, 10^5].

Solution Approach

• Given 2 binary search trees, the requirement is to sort the values of all nodes in the 2 trees in ascending order.
• The simplest brute-force method for this problem is to traverse all nodes of the 2 trees, put them into an array, and then sort the array from smallest to largest. Although this can AC, the time complexity is high, because it does not use the condition that the given trees are binary search trees. Since the nodes in the trees are already ordered, the essence of the problem is to merge 2 sorted arrays. Use inorder traversal to traverse all node values of the 2 binary search trees; after traversal, the values are sorted. Then merge these two sorted arrays. Merging 2 sorted arrays is Problem 88.

Code

// Solution 1: merge and sort
func getAllElements(root1 *TreeNode, root2 *TreeNode) []int {
	arr1 := inorderTraversal(root1)
	arr2 := inorderTraversal(root2)
	arr1 = append(arr1, make([]int, len(arr2))...)
	merge(arr1, len(arr1)-len(arr2), arr2, len(arr2))
	return arr1
}

// Solution 2: brute-force traversal and sorting, with high time complexity
func getAllElements1(root1 *TreeNode, root2 *TreeNode) []int {
	arr := []int{}
	arr = append(arr, preorderTraversal(root1)...)
	arr = append(arr, preorderTraversal(root2)...)
	sort.Ints(arr)
	return arr
}