Daily bit(e) of C++ | Validating a complete binary tree
Daily bit(e) of C++ #154, Common interview problem: validating a complete binary tree
Today, we will look at a common interview problem: Validating a complete binary tree.
Given a binary tree, determine whether the tree is complete. A complete binary tree can only have missing nodes on the last level, and those nodes must be in the leftmost positions.
For example, in the above picture, the second tree is not a complete binary tree since the node on the last level is not in the leftmost position.
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/5q3dE6fWW.
Solution
We could solve this problem using breadth-first search, which naturally provides a level-order traversal. If, while traversing, we visit a non-null node after visiting a null node, we know this tree is incomplete.
However, breadth-first search has space complexity of O(n). We can reduce this to O(depth) using a depth-first search.
Consider that a binary tree can be flattened into an array, with node i having its left child at index 2i+1 and right child at index 2i+2.
In a complete binary tree, we know that the highest index of a node in the tree is the total number of nodes minus one. Therefore we can check this condition.
The tree is complete if, during our traversal, we only visit indexes from the range [0, total-1].
