Daily bit(e) of C++ | Column-order traversal
Daily bit(e) of C++ #14, Common interview question: Column-order traversal
Today, we will look at another common interview question—the column-order traversal for a binary tree.
Given a binary tree, implement a column-order traversal of the tree. The nodes should be traversed in the order of their column, where the column of a child is either -1 (for the left child) or +1 (for the right child) from its parent. Nodes in the same column should be traversed by their distance from the root node or by the node value if they are also the same distance from the root.
As an example, the column order traversal of this tree is: {4, 2, 1, 5, 6, 3, 7}.
Before you continue to read the solution, try to solve it yourself. Here is a Compiler Explorer link with a couple of test cases: https://compiler-explorer.com/z/zEGMnx3jn.
Solution
The main complication we have is that no matter where in the traversal we are, we can still reach any column.
This effectively forces us to sort the nodes (in some fashion).
The most straightforward approach to sort the nodes is to use an ordered data structure (such as std::set or std::priority_queue). Each insert into an ordered data structure is O(logn), and since we will insert each node, the final complexity is O(n*logn).
After filling our data structure, we can traverse it in linear time, visiting each node.
