Binary Tree Zigzag Level Order Traversal

Problem Statement

Given the root of a binary tree, return the zigzag level order traversal of its nodes’ values. (i.e., from left to right, then right to left for the next level and alternate between).

Examples

Input	Output
[3,9,20,null,null,15,7]	[[3],[20,9],[15,7]]
[1]	[[1]]
[]	[]

Constraints

• The number of nodes in the tree is in the range [0, 2000].
• -1000 <= Node.val <= 1000

Real-World Applications

Where this pattern appears

• File system hierarchies and directory structures
• DOM tree manipulation in web browsers
• XML/JSON parsing and configuration management
• Organizational hierarchies and permission trees

Complexity Comparison

Approach	Time	Space
BFS with Deque	O(n)	O(w)
DFS with Level Parity	O(n)	O(h)

Approach 1: BFS with Deque (Recommended)

★ Recommended

Use a deque. For even levels, add from left; for odd levels, add from right.

⏱ Time O(n) 💾 Space O(w)

Solution Code

Python

binary_tree_zigzag_level_order_traversal_deque.py

from typing import Optional, List
from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def zigzagLevelOrder(root: Optional[TreeNode]) -> List[List[int]]:
    if not root: return []
    result = []
    queue = deque([root])
    level = 0
    while queue:
        sz = len(queue)
        level_values = deque()
        for _ in range(sz):
            node = queue.popleft()
            if level % 2 == 0:
                level_values.append(node.val)
            else:
                level_values.appendleft(node.val)
            if node.left: queue.append(node.left)
            if node.right: queue.append(node.right)
        result.append(list(level_values))
        level += 1
    return result

if __name__ == "__main__":
    root = TreeNode(3)
    root.left, root.right = TreeNode(9), TreeNode(20)
    root.right.left, root.right.right = TreeNode(15), TreeNode(7)
    print(zigzagLevelOrder(root))

C++

binary_tree_zigzag_level_order_traversal_deque.cpp

#include <iostream>
#include <vector>
#include <deque>
#include <queue>
using namespace std;

struct TreeNode { int val; TreeNode *left, *right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} };

vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
    vector<vector<int>> result;
    if (!root) return result;
    queue<TreeNode*> q; q.push(root);
    int level = 0;
    while (!q.empty()) {
        int sz = q.size(); deque<int> dq;
        for (int i = 0; i < sz; i++) {
            TreeNode* n = q.front(); q.pop();
            if (level % 2 == 0) dq.push_back(n->val);
            else dq.push_front(n->val);
            if (n->left) q.push(n->left);
            if (n->right) q.push(n->right);
        }
        result.push_back(vector<int>(dq.begin(), dq.end()));
        level++;
    }
    return result;
}

Java

binary_tree_zigzag_level_order_traversal_deque.java

import java.util.*;

public class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
        Queue<TreeNode> q = new LinkedList<>(); q.offer(root);
        int level = 0;
        while (!q.isEmpty()) {
            int sz = q.size(); Deque<Integer> dq = new LinkedList<>();
            for (int i = 0; i < sz; i++) {
                TreeNode n = q.poll();
                if (level % 2 == 0) dq.offer(n.val);
                else dq.offerFirst(n.val);
                if (n.left != null) q.offer(n.left);
                if (n.right != null) q.offer(n.right);
            }
            result.add(new ArrayList<>(dq));
            level++;
        }
        return result;
    }
    public static class TreeNode { int val; TreeNode left, right; TreeNode(int x) { val = x; } }
}

JavaScript

binary_tree_zigzag_level_order_traversal_deque.js

function TreeNode(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; }

function zigzagLevelOrder(root) {
    const result = []; if (!root) return result;
    const q = [root]; let level = 0;
    while (q.length) {
        const sz = q.length, dq = [];
        for (let i = 0; i < sz; i++) {
            const n = q.shift();
            if (level % 2 === 0) dq.push(n.val);
            else dq.unshift(n.val);
            if (n.left) q.push(n.left);
            if (n.right) q.push(n.right);
        }
        result.push(dq);
        level++;
    }
    return result;
}
module.exports = zigzagLevelOrder;

Rust

binary_tree_zigzag_level_order_traversal_deque.rs

use std::cell::RefCell; use std::collections::VecDeque; use std::rc::Rc;
#[derive(Debug)]
pub struct TreeNode { pub val: i32, pub left: Option<Rc<RefCell<TreeNode>>>, pub right: Option<Rc<RefCell<TreeNode>>>, }
pub fn zigzag_level_order(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<Vec<i32>> {
    let mut result = Vec::new(); if root.is_none() { return result; }
    let mut q = VecDeque::new(); q.push_back(root.unwrap());
    let mut level = 0;
    while !q.is_empty() { let sz = q.len(); let mut level_vals = VecDeque::new();
        for _ in 0..sz { let n = q.pop_front().unwrap(); let n_ref = n.borrow_mut();
            if level % 2 == 0 { level_vals.push_back(n_ref.val); }
            else { level_vals.push_front(n_ref.val); }
            if let Some(l) = n_ref.left.clone() { q.push_back(l); }
            if let Some(r) = n_ref.right.clone() { q.push_back(r); }
        }
        result.push(level_vals.into_iter().collect());
        level += 1;
    }
    result
}

Go

binary_tree_zigzag_level_order_traversal_deque.go

package main

type TreeNode struct { Val int; Left, Right *TreeNode }

func ZigzagLevelOrder(root *TreeNode) [][]int {
    var result [][]int; if root == nil { return result }
    queue := []*TreeNode{root}; level := 0
    for len(queue) > 0 {
        sz := len(queue); var levelVals []int
        for i := 0; i < sz; i++ {
            n := queue[0]; queue = queue[1:]
            if level%2 == 0 { levelVals = append(levelVals, n.Val) }
            else { levelVals = append([]int{n.Val}, levelVals...) }
            if n.Left != nil { queue = append(queue, n.Left) }
            if n.Right != nil { queue = append(queue, n.Right) }
        }
        result = append(result, levelVals)
        level++
    }
    return result
}

Approach 2: DFS with Level Parity

🎯 Interview Favourite

Use DFS and check level parity to determine insertion direction.

⏱ Time O(n) 💾 Space O(h)

Solution Code

Python

binary_tree_zigzag_level_order_traversal_parity.py

from typing import Optional, List

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def zigzagLevelOrder(root: Optional[TreeNode]) -> List[List[int]]:
    result = []
    def dfs(node: Optional[TreeNode], level: int):
        if not node: return
        if level == len(result): result.append([])
        if level % 2 == 0:
            result[level].append(node.val)
        else:
            result[level].insert(0, node.val)
        dfs(node.left, level + 1)
        dfs(node.right, level + 1)
    dfs(root, 0)
    return result

if __name__ == "__main__":
    root = TreeNode(3)
    root.left, root.right = TreeNode(9), TreeNode(20)
    root.right.left, root.right.right = TreeNode(15), TreeNode(7)
    print(zigzagLevelOrder(root))

C++

binary_tree_zigzag_level_order_traversal_parity.cpp

#include <iostream>
#include <vector>
using namespace std;

struct TreeNode { int val; TreeNode *left, *right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} };

void dfs(TreeNode* n, int level, vector<vector<int>>& result) {
    if (!n) return;
    if (level == result.size()) result.push_back({});
    if (level % 2 == 0) result[level].push_back(n->val);
    else result[level].insert(result[level].begin(), n->val);
    dfs(n->left, level + 1, result);
    dfs(n->right, level + 1, result);
}

vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
    vector<vector<int>> result;
    dfs(root, 0, result);
    return result;
}

Java

binary_tree_zigzag_level_order_traversal_parity.java

import java.util.*;

public class Solution {
    void dfs(TreeNode n, int level, List<List<Integer>> result) {
        if (n == null) return;
        if (level == result.size()) result.add(new ArrayList<>());
        if (level % 2 == 0) result.get(level).add(n.val);
        else result.get(level).add(0, n.val);
        dfs(n.left, level + 1, result);
        dfs(n.right, level + 1, result);
    }
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        dfs(root, 0, result);
        return result;
    }
    public static class TreeNode { int val; TreeNode left, right; TreeNode(int x) { val = x; } }
}

JavaScript

binary_tree_zigzag_level_order_traversal_parity.js

function TreeNode(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; }

function zigzagLevelOrder(root) {
    const result = [];
    function dfs(n, level) {
        if (!n) return;
        if (level === result.length) result.push([]);
        if (level % 2 === 0) result[level].push(n.val);
        else result[level].unshift(n.val);
        dfs(n.left, level + 1);
        dfs(n.right, level + 1);
    }
    dfs(root, 0);
    return result;
}
module.exports = zigzagLevelOrder;

Rust

binary_tree_zigzag_level_order_traversal_parity.rs

use std::cell::RefCell; use std::rc::Rc;
#[derive(Debug)]
pub struct TreeNode { pub val: i32, pub left: Option<Rc<RefCell<TreeNode>>>, pub right: Option<Rc<RefCell<TreeNode>>>, }
pub fn zigzag_level_order(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<Vec<i32>> {
    let mut result = Vec::new();
    fn dfs(n: &Option<Rc<RefCell<TreeNode>>>, level: usize, result: &mut Vec<Vec<i32>>) {
        if let Some(node) = n {
            let node_ref = node.borrow();
            if level == result.len() { result.push(Vec::new()); }
            if level % 2 == 0 { result[level].push(node_ref.val); }
            else { result[level].insert(0, node_ref.val); }
            dfs(&node_ref.left, level + 1, result);
            dfs(&node_ref.right, level + 1, result);
        }
    }
    dfs(&root, 0, &mut result);
    result
}

Go

binary_tree_zigzag_level_order_traversal_parity.go

package main

type TreeNode struct { Val int; Left, Right *TreeNode }

func ZigzagLevelOrder(root *TreeNode) [][]int {
    var result [][]int
    var dfs func(*TreeNode, int)
    dfs = func(n *TreeNode, level int) {
        if n == nil { return }
        if level == len(result) { result = append(result, []int{}) }
        if level%2 == 0 { result[level] = append(result[level], n.Val) }
        else { result[level] = append([]int{n.Val}, result[level]...) }
        dfs(n.Left, level + 1)
        dfs(n.Right, level + 1)
    }
    dfs(root, 0)
    return result
}

Interview Tips

Key trade-offs to discuss

• Time vs. space trade-offs between approaches
• Handling edge cases (empty inputs, single elements, duplicates)
• Optimization opportunities and when they matter
• Follow-up variations and constraint changes