Solution Review: Check Completeness of Tree Using Queue

Solution

We’ll perform a breadth-first traversal on the tree using a queue. Because every level in the complete tree is filled (every node has both left and right children), if we get a node that does not have a left child then it cannot have a right child. Similarly, if we find a node that does not have any child, then no other node in breadth-first traversal can have any child. Let us see this in action.