Search⌘ K
Home
Courses
Decode the Coding Interview in Swift: Real-World Examples

Binary Tree Zigzag Level Order Traversal

Understand how to traverse a binary tree in zigzag level order using a modified breadth-first search. Learn to use a deque structure to alternate between left-to-right and right-to-left traversal on each level. This lesson covers the approach, implementation steps, and analyzes time and space complexity for efficient tree traversal.

We'll cover the following...

Description

Given a binary tree T, you have to find its nodes’ zigzag level order traversal. The zigzag level order traversal corresponds to traversing nodes from left to right and then right to left for the next level, alternating between.

You have to return the element in each level in a two-dimensional array.

Let’s look at an example:

Do it yourself

Swift
import Swift
func zigzagLevelOrder(root: TreeNode?) -> [[Int]] {
    return [[]]        
}
Binary tree zigzag level order traversal exercise

Solution

As per the problem statement, we need to traverse the tree in a level-by-level zigzag order. An intuitive approach for this problem would be to use Breadth-First Search (BFS). By default, BFS provides ordering from left to right within a single level.

We will need to modify BFS a little to get our desired output, a zigzagzigzag ...