all programming  

  Sep 05, 2020

Day 5

A tree question that I knew.

The Question

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

The Process

Note: My calculation of time complexity on this, is in no way, rigorous. A rigorous time complexity analysis is welcome, and so are more efficient solutions/improvements, although O(n1 + n2) lower-bounds all solutions’ runtime ( n1, n2 being the number of elements in in root1, root2), respectively. This is simply because you can’t do better, and at the very least, will have to visit each element.

Algorithm

  • The ideas here are pretty simple. However, before reading on, I recommend that you look up inorder traversal and also solve the problem of merging two sorted lists. Read on only after you still have no idea on how to go about approaching this question.
  • Note that you know the trees provided to us satisfy binary tree constraints, i.e. an inorder traversal/walk would yield elements in a sorted order. If you have a list in your hand, you can actually create a sorted list during your inorder walk/traversal.
  • You also understand that eventually, you want a sorted list.
  • Hence, would it be easy for us to first kind of flatten both the trees into sorted lists, and then merge these two sorted lists? Yes! * This is a rather straightforward question. Besides what the explanation covers, does anything else confuse you? Feel free to post that as a comment!

Time Complexity Time complexity here is very straightforward. You have two root nodes i.e. two trees. Call them T1 and T2. Let n1, n2 be the number of TreeNodes in T1 and T2, respectively. First, you do an inorder traversal of each of both T1 and T2, and get two sorted lists. This takes O(n1 + n2) since you visit each element in both trees exactly once. After this, you merge the two sorted lists i.e. another computation that costs O(n1 + n2) (since that’s the total number of elements in both the lists combined. Therefore, overall time complexity => O(n1 + n2).


The Code

public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
        List<Integer> list1 = inorder(root1, new ArrayList<>());
        List<Integer> list2 = inorder(root2, new ArrayList<>());
        return merge(list1, list2);
    }
    /**
    * Provided a root node, this function returns a sorted list of the tree's elements using
    * inorder traversal.
    **/
    public List<Integer> inorder(TreeNode root, List<Integer> list) {
        if (root == null) {
            return list;
        }

        if (root.left == null && root.right == null) {
            list.add(root.val);
            return list;
        }

        inorder(root.left, list);
        list.add(root.val);
        inorder(root.right, list);

        return list;
    }


    /**
    * Given two sorted lists, list1 and list2, we create a sorted output list that is a union
    * of all the elements in list1 and list2.
    **/
    public List<Integer> merge(List<Integer> list1, List<Integer> list2) {
        List<Integer> res = new ArrayList<Integer>(list1.size() + list2.size());

        int i = 0;
        int j = 0;

        while (i < list1.size() && j < list2.size()) {
            if (list1.get(i) <= list2.get(j)) {
                res.add(list1.get(i));
                i++;
                continue;
            }

            if (list1.get(i) > list2.get(j)) {
                res.add(list2.get(j));
                j++;
            }
        }

        if (i < list1.size()) {
            for (int remaining = i; remaining < list1.size(); remaining++) {
                res.add(list1.get(i));
                i++;
            }
        }

        if (j < list2.size()) {
            for (int remaining = j; remaining < list2.size(); remaining++) {
                res.add(list2.get(j));
                j++;
            }
        }

        return res;
    }