< Back





1305. All Elements in Two Binary Search Trees

We have the return the elements from two binary search trees in ascending order. Little known fact
about binary search trees, if you process the nodes in-order, you can retrieve the contents in
ascending order. There's two ways we can go about this - we could process each tree separately in
O(n) time, creating a list of the elements in each tree sorted in ascending order, and the merging
the two lists. We could also process them simultaneously and iteratively.

To iteratively process the two binary trees simultaneously, we're going to have to use stacks to
emulate an in-order traversal. Just like we would do recursively, we travel all the way down the
left side of each binary search tree, pushing the nodes onto the stack until we hit None.

Then, we compare the top nodes of the two stacks. Which ever node has the smaller value gets popped
and its value appended to the answer array. Then, like we normally do for an in-order traversal, we
process the right node of the just popped node.

The solution is as follows:


  class Solution:
      def getAllElements(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> List[int]:
          stack1, stack2, ans = [], [], []

          while root1 or root2 or stack1 or stack2:
              while root1:
                  _, root1 = stack1.append(root1), root1.left
              while root2:
                  _, root2 = stack2.append(root2), root2.left

              if not stack2 or stack1 and stack1[-1].val < stack2[-1].val:
                  root1 = stack1.pop()
                  _, root1 = ans.append(root1.val), root1.right
              else:
                  root2 = stack2.pop()
                  _, root2 = ans.append(root2.val), root2.right

          return ans


_ Time Complexity:

  O(n + m) - Where n and m are the size of each binary search tree.

_ Space Complexity:

  O(n + m) - We maintain the output and both stacks.