Leetcode discuss: 1305. All Elements in Two Binary Search Trees

 Here is the link. 

C# preorder traversal of binary search tree and then merge two sorted list

August 31, 2020
1305. All Elements in Two Binary Search Trees

I tried to think about using O(1) space to solve the problem, but I could not figure out the solution. The naive solution is to preorder traverse two binary searach tree first, and then merge two sorted lists.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
   public  IList<int> GetAllElements(TreeNode root1, TreeNode root2)
        {
            var list1 = new List<int>();
            var list2 = new List<int>(); 

            inorderTraversal(root1, list1);
            inorderTraversal(root2, list2); 
                       
            return mergeTwoSortedLists(list1, list2);            
        }

        private static void inorderTraversal(TreeNode root, List<int> list)
        {
            if(root == null)
            {
                return; 
            }

            inorderTraversal(root.left, list);

            list.Add(root.val);

            inorderTraversal(root.right, list);
        }

        private static List<int> mergeTwoSortedLists(List<int> list1, List<int> list2)
        {
            var merged = new List<int>(); 

            if (list1 == null || list1.Count == 0)
            {
                merged = new List<int>(list2);
                return merged; 
            }

            if (list2 == null || list2.Count == 0)
            {
                merged = new List<int>(list1);
                return merged;
            }

            var length1 = list1.Count;
            var length2 = list2.Count;

            int index1 = 0;
            int index2 = 0;

            while (index1 < length1 || index2 < length2)
            {
                if (index1 == length1)
                {
                    merged.Add(list2[index2]);
                    index2++;
                }
                else if (index2 == length2)
                {
                    merged.Add(list1[index1]);
                    index1++;
                }
                else
                {
                    var current1 = list1[index1];
                    var current2 = list2[index2];
                    if (current1 <= current2)
                    {
                        merged.Add(current1);
                        index1++;
                    }
                    else
                    {
                        merged.Add(current2);
                        index2++;
                    }
                }
            }

            return merged; 
        }
}