1305. All Elements in Two Binary Search Trees

UnknownView on LeetCode

Tree Depth-First Search Binary Search Tree Sorting Binary Tree

Time: O(m+n)

Space: O(m+n)

Problem Overview

In-order traversal of a BST yields sorted values.

Intuition

In-order traversal of a BST yields sorted values. Traverse both trees to get two sorted arrays, then merge with the standard two-pointer technique — same as merging two sorted lists in merge sort.

Algorithm

1In-order DFS on root1 into list A; same for root2 into list B.
2Initialize pointers i = 0, j = 0 and empty result.
3While both pointers in range: append smaller of A[i], B[j] and advance that pointer.
4Append remaining elements from whichever list is not exhausted.
5Return merged array.

Example Walkthrough

Input: root1 = [2,1,4], root2 = [1,3]

1.In-order: A = [1,2,4], B = [1,3].
2.Merge: 1,1,2,3,4.

Output: [1, 1, 2, 3, 4]

Common Pitfalls

•Do not use a heap unless asked — two sorted arrays merge in O(m+n).
•Iterative in-order avoids stack overflow on skewed trees.
•Duplicates are kept — merge does not deduplicate.

1305.cs

// Approach: In-order traversal of each BST produces sorted lists; merge the two sorted lists.
// Time: O(m+n) Space: O(m+n)

public class TreeNode
{
    private Stack<TreeNode> stack = new Stack<TreeNode>();

    public BSTIterator(TreeNode root)
    {
        PushLeftsUntilNull(root);
    }

    public int Peek()
    {
        return stack.Peek().val;
    }

    public void Next()
    {
        PushLeftsUntilNull(stack.Pop().right);
    }

    public bool HasNext()
    {
        return stack.Count > 0;
    }

    private void PushLeftsUntilNull(TreeNode node)
    {
        while (node != null)
        {
            stack.Push(node);
            node = node.left;
        }
    }
}

public class Solution
{
    public IList<int> GetAllElements(TreeNode root1, TreeNode root2)
    {
        List<int> ans = new List<int>();
        BSTIterator bstIterator1 = new BSTIterator(root1);
        BSTIterator bstIterator2 = new BSTIterator(root2);

        while (bstIterator1.HasNext() && bstIterator2.HasNext())
        {
            if (bstIterator1.Peek() < bstIterator2.Peek())
            {
                ans.Add(bstIterator1.Peek());
                bstIterator1.Next();
            }
            else
            {
                ans.Add(bstIterator2.Peek());
                bstIterator2.Next();
            }
        }

        while (bstIterator1.HasNext())
        {
            ans.Add(bstIterator1.Peek());
            bstIterator1.Next();
        }

        while (bstIterator2.HasNext())
        {
            ans.Add(bstIterator2.Peek());
            bstIterator2.Next();
        }

        return ans;
    }
}

Was this solution helpful?