All Elements in Two Binary Search Trees Solution
Leetcode Solution: Understand Leetcode problem All Elements in Two Binary Search Trees(1305) Solution
In this article we’ll be solving the problem: All Elements in Two Binary Search Trees. Just like the problem, Minimum Absolute Difference in BST and Increasing order Search Tree, this problem falls into the category of BST problems in which we traverse the tree in not-decreasing order if we use In Order tree traversal approach.
Given two binary search trees root1 and root2.
Return a list containing all the integers from both trees sorted in ascending order.
Example 1:
2 1
/ \ / \
1 4 0 3
Input: root1 = [2,1,4], root2 = [1,0,3]
Output: [0,1,1,2,3,4]
Constraints:
Each tree has at most 5000 nodes.
Each node's value is between [-10^5, 10^5].
We know that if we perform an In Order tree traversal on a binary search tree then we’ll get the elements of the tree in a non decreasing order. So, if we perform it on both the input trees then we’ll get the two non decreasing lists from our input trees and half of the problem will be solved!
The next problem we’ve to solve is to merge both those lists. Here’s an image showing the tree traversal and the merge operations that we’ll perform on the input trees:
Here is the program for that:
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func getAllElements(root1 *TreeNode, root2 *TreeNode) []int {
if root1 == nil && root2 == nil {
return nil
}
var list1 []int
if root1 != nil {
list1 = inOrder(root1, list1)
}
var list2 []int
if root2 != nil {
list2 = inOrder(root2, list2)
}
if len(list1) == 0 {
return list2
}
if len(list2) == 0 {
return list1
}
var list3 []int
for i, j := 0, 0;; {
var elem1 int
if len(list1) > i {
elem1 = list1[i]
} else {
// we add the remaining elements from list2 into list3
// there are no elements in list1
if len(list2) > j {
list3 = append(list3, list2[j:]...)
break
}
}
var elem2 int
if len(list2) > j {
elem2 = list2[j]
} else {
// we add the remaining elements from list1 into list3
// there are no elements in list2
if len(list1) > i {
list3 = append(list3, list1[i:]...)
break
}
}
if elem1 < elem2 {
list3 = append(list3, elem1)
i++
} else {
list3 = append(list3, elem2)
j++
}
}
return list3
}
func inOrder(node *TreeNode, list []int) []int {
if node.Left != nil {
list = inOrder(node.Left, list)
}
list = append(list, node.Val)
if node.Right != nil {
return inOrder(node.Right, list)
}
return list
Here, the function getAllElements call the function inOrder to perform the in order tree traversal on the input trees.
inOrder returns a list of the elements in the non decreasing order as the input trees are BSTs. list1 and list2
store the elements for the 1st and the 2nd tree. Then we create a new list, list3, that’ll contain the merged contents
from both the lists.
This program can be found on GitHub as well.
