InterviewCrunch

Beta

Binary Tree Zigzag Traversal

Easy

Question

Given the root of a binary tree, return a list that includes sublists of nodes from each level. The nodes within each sublist should alternate in order between left to right and right to left.

Binary Tree Zigzag Traversal Example 1

Input: root = [1, 2, 3, 4, None, 6, 7]

Output: [[1], [3, 2], [4, 6, 7]]

The first level lists nodes from left to right: 1. The next level lists nodes from right to left: 3, 2. The next level lists nodes from left to right again: 4, 6, 7.

Binary Tree Zigzag Traversal Example 2

Input: root = [1, 2, 3, 4, 5, 6, None, 8, 9, None, None, 12]

Output: [[1], [3, 2], [4, 5, 6], [12, 9, 8]]

Binary Tree Zigzag Traversal Example 3

Input: root = [1, None, 3, None, None, None, 7]

Output: [[1], [3], [7]]

Clarify the problem

What are some questions you'd ask an interviewer?

Understand the problem

What is the zigzag traversal output given the root of this tree? root = [5, 7, 3, 9, 7, None, 2]
[[5], [7, 3], [9, 7, 2]]
[[5], [3, 7], [9, 7, 2]]
[[5], [7, 3], [9, 7, None, 2]]
[[5], [3, 7], [9, 7, 2]]

Login or signup to save your code.

Notes

PrevMaximum Width of Binary Tree
NextSymmetric Tree