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

September 6, 2020The 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: