Daily bit(e) of C++ | Construct a binary max-tree
Daily bit(e) of C++ #273, Common interview problem: Construct a binary max-tree.
Today, we will look at a common C++ interview problem: Construct a binary max-tree.
Given an array of unique integers, construct a binary max-tree. A max tree is constructed by picking the maximum element as the root; all elements to the left of the maximum belong to the left child subtree, and all elements to the right belong to the right subtree. Both subtrees recursively follow the same logic.
Before you continue reading the solution, I encourage you to try to solve it yourself. Here is a Compiler Explorer link with a couple of test cases: https://compiler-explorer.com/z/vndE9sj55.
Solution
A straightforward solution essentially mirrors the problem formulation. We can scan for the maximum value and then recurse on the prefix and suffix, ending with O(n*n) complexity.
However, we can do a lot better. Let’s consider traversing the elements from left to right.
As long as the values are descending, we can keep adding them as the right child of the previous element. However, once we encounter a local maxima, we need to find the correct place for it. This element will be the right child of the next higher value we have seen, and the entire subtree of lower elements will be its left child.
We could achieve this by using an ordered container; however, we can also use a monotonic stack because we will not revisit the nodes designated as the lower values and assigned as the left subtree of the inserted element. With a monotonic stack, we end up with O(n) overall complexity.
