Codiwan.com

The blog for Design Patterns, Linux, HA and Myself!

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:

Example Tree Traversal

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.

Loading Comments... Disqus Loader
comments powered by Disqus