Level Order Traversal of Binary Tree
Problem Statement#
Given the root of a binary tree, display the node values at each level. Node values for all levels should be displayed on separate lines. Let’s take a look at the below binary tree.
Solution#
Solution Explanation#
Runtime Complexity#
The runtime complexity of this solution is linear, O(n)O(n).
Memory Complexity#
The memory complexity of this solution is linear, O(n)O(n).
Solution Breakdown#
Initialize a queue,
queue, with the root node.Iterate over the
queueuntil it’s empty:For each level, calculate the size
(level_size)of the queue.Initialize an empty list
level_nodes.Iterate
level_sizetimes:Dequeue a node from the
queue.Append the value of the dequeued node in
level_nodes.Enqueue the left child and the right child of the dequeued node in
queue, if they exist.
Convert
level_nodesto a comma-separated string and store it inresult.
Return the
result.
Practice problems like this and many more by checking out our Grokking the Coding Interview: Patterns for Coding Questions course!