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.
Level order traversal for this tree should look like: 100; 50, 200; 25, 75, 350
Hint
- Breadth first traversal
Try it yourself
def level_order_traversal(root):result = ""#TODO: Write - Your - Codereturn result
Solution
from collections import dequedef level_order_traversal(root):result = []if not root:result = "None"return resultqueue = deque()queue.append(root)while queue:level_size = len(queue)level_nodes = []for _ in range(level_size):temp = queue.popleft()level_nodes.append(str(temp.data))if temp.left:queue.append(temp.left)if temp.right:queue.append(temp.right)result.append(", ".join(level_nodes))return "; ".join(result)arr = [100,50,200,25,75,350]root = create_BST(arr)print("InOrder Traversal:", end = "")display_inorder(root)print("\nLevel Order Traversal: ", level_order_traversal(root))
Solution Explanation
Runtime Complexity
The runtime complexity of this solution is linear, .
Memory Complexity
The memory complexity of this solution is linear, .
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.
- Dequeue a node from the
- Convert
level_nodesto a comma-separated string and store it inresult.
- For each level, calculate the size
-
Return the
result.
Practice problems like this and many more by checking out our Grokking the Coding Interview: Patterns for Coding Questions course!
TRENDING TOPICS
