Search⌘ K
AI Features
Home
Courses
Decode the Coding Interview in Kotlin: Real-World Examples

Binary Tree Zigzag Level Order Traversal

Explore how to implement binary tree zigzag level order traversal in Kotlin using Breadth-First Search and a deque. Understand alternating traversal from left to right and right to left on each level. This lesson helps you apply these techniques to solve coding problems involving tree data structures efficiently.

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 elements in each level in a two-dimensional array.

Let’s look at an example:

Coding Exercise

Kotlin 1.5
internal object Solution {

    fun zigzagLevelOrder(root: TreeNode?): List<List<Int>> {

        // write your code here

        return ArrayList()

    }

}
Binary Tree Zigzag Level Order Traversal

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 ...