Level order traversal is a breadth-first traversal of a binary tree in which every node at a given depth is visited before any node at the next deeper level. Because a binary tree provides only downward links, the traversal cannot be performed with a single moving pointer; instead a FIFO queue holds the references of *discovered* nodes (known but not yet visited), and the algorithm repeatedly dequeues a node, visits it, and enqueues its non-null children until the queue is empty. This is the tree-traversal counterpart of breadth-first search in graph theory, and it runs in O(n) time for all cases with O(n) extra space in the average and worst case (O(1) for a degenerate one-child-per-node tree).
Level order traversal is a breadth-first traversal of a binary tree in which every node at a given depth is visited before any node at the next deeper level. Because a binary tree provides only downw…