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 nodes in
. Having two sorted lists of size and , we can
merge them in a new sorted list in . With these two
building blocks, we can produce an algorithm to return the sorted list of all
integers of both trees in , being the number of
nodes in the first tree, and being the number of nodes in the second tree.
The following is an implementation of that idea: