Problem statement

Given the root of a binary tree, return the values of all nodes on its odd levels, where the root is on level 1, its children on level 2, and so on.

List them in level order: level 1, then level 3, then level 5, …, and within a level from left to right.

Example 1

Input: root = [1,2,3,4,5,null,6,null,null,7,8]
Output: [1,4,5,6]
Explanation: Level 1 holds 1, level 3 holds 4, 5 and 6; levels 2 and 4 are even.

Example 2

Input: root = [1,2,3]
Output: [1]
Explanation: Only the root's level is odd.

Example 3

Input: root = [5,null,9,8]
Output: [5,8]
Explanation: 5 is on level 1 and 8 on level 3.

Constraints

• 1 <= number of nodes <= 10^3
• 1 <= Node.val <= 10^3

Hints for Nodes at Odd Levels

1. Hint 1

   You need to know each node's level — process the tree one level at a time.

2. Hint 2

   A breadth-first search with a queue, taking one whole level per round, tells you which level you are on.

3. Hint 3

   Keep a level counter starting at 1 and collect the round's values only when it is odd.

How to solve Nodes at Odd Levels

Level-order traversal visits the tree level by level and, within a level, left to right — exactly the required output order. Counting the rounds gives the level number.

Approach

1. Start with a queue holding the root and level = 1.
2. While the queue is not empty, take the size nodes currently in it — one full level.
3. If level is odd, append their values in order. Enqueue each node's left then right child.
4. Increase level and repeat.

Why it works

At the start of each round the queue holds exactly the nodes of one level, in left-to-right order, because children are enqueued left before right and parents are processed in order.

Complexity

• Time — O(n)
• Space — O(w), w the widest level

Pitfalls

• Levels count from 1 at the root, so the root is always included.
• A depth-first search can find the odd-level nodes too, but it lists them in a different order from the one required.

Reference solution

Python

from typing import List, Optional

def nodesAtOddLevels(root: Optional[TreeNode]) -> List[int]:
    out = []
    level = [root] if root else []
    depth = 1
    while level:
        if depth % 2 == 1:
            out.extend(node.val for node in level)
        nxt = []
        for node in level:
            if node.left:
                nxt.append(node.left)
            if node.right:
                nxt.append(node.right)
        level = nxt
        depth += 1
    return out

Java

public static int[] nodesAtOddLevels(TreeNode root) {
    List<Integer> out = new ArrayList<>();
    Deque<TreeNode> queue = new ArrayDeque<>();
    if (root != null) queue.add(root);
    int level = 1;
    while (!queue.isEmpty()) {
        for (int i = queue.size(); i > 0; i--) {
            TreeNode node = queue.poll();
            if (level % 2 == 1) out.add(node.val);
            if (node.left != null) queue.add(node.left);
            if (node.right != null) queue.add(node.right);
        }
        level++;
    }
    int[] res = new int[out.size()];
    for (int i = 0; i < res.length; i++) res[i] = out.get(i);
    return res;
}

C++

vector<int> nodesAtOddLevels(TreeNode* root) {
    vector<int> out;
    queue<TreeNode*> q;
    if (root) q.push(root);
    int level = 1;
    while (!q.empty()) {
        for (int i = (int) q.size(); i > 0; i--) {
            TreeNode* node = q.front();
            q.pop();
            if (level % 2 == 1) out.push_back(node->val);
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        level++;
    }
    return out;
}

JavaScript

var nodesAtOddLevels = function(root) {
    var out = [];
    if (root === null) return out;
    var queue = [root], head = 0, level = 1;
    while (head < queue.length) {
        var end = queue.length;
        for (; head < end; head++) {
            var node = queue[head];
            if (level % 2 === 1) out.push(node.val);
            if (node.left !== null) queue.push(node.left);
            if (node.right !== null) queue.push(node.right);
        }
        level++;
    }
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More breadth-first search problems

• Level of a Node in Binary Tree Easy
• Sum of Leaf Nodes at Minimum Level Easy
• Count BST Nodes That Lie in a Given Range Easy
• Kth Largest Element in BST Easy
• Ceil in BST Easy
• Nodes at Distance K from Root Easy