# September LeetCoding Challenge, Day 5: All Elements in Two Binary Search Trees

September 6, 2020

This is part of a series of posts about the September LeetCoding Challenge. Check the first post for more information.

The problem for September 5 is All Elements in Two Binary Search Trees. We’re interested in, given two binary search trees of integers, returning a sorted list of all the integers from both trees.

Since we’re dealing with binary search trees here, each node is guaranteed to store a key greater than all the keys in the node’s left subtree and less than those in its right subtree. As such, an in-order traversal of the tree is guaranteed to produce a sorted list of its elements. We can do an in-order traversal of a binary tree with $$n$$ nodes in $$\mathcal{O}(n)$$. Having two sorted lists of size $$a$$ and $$b$$, we can merge them in a new sorted list in $$\mathcal{O}(a + b)$$. With these two building blocks, we can produce an algorithm to return the sorted list of all integers of both trees in $$\mathcal{O}(n + m)$$, $$n$$ being the number of nodes in the first tree, and $$m$$ being the number of nodes in the second tree. The following is an implementation of that idea: