Binary Tree Level Order Traversal

📋

Problem

Imagine you want to send a message to everyone in a company, starting from the CEO and moving level by level down the hierarchy. How do you visit each employee in order of their level?

Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level). Input: root node of a binary tree. Output: a list of lists, where each inner list contains the values of nodes at that level.

The number of nodes in the tree is in the range [1, 10^5].Node values are integers and can be positive, negative, or zero.

Edge cases: Single node tree → [[root_value]]Tree with only left children → each level has one nodeTree with only right children → each level has one node

</>

IDE

def levelOrder(root: Optional[TreeNode]) -> List[List[int]]:public List<List<Integer>> levelOrder(TreeNode root)vector<vector<int>> levelOrder(TreeNode* root)function levelOrder(root)

def levelOrder(root: Optional[TreeNode]) -> List[List[int]]:
    # Write your solution here
    pass

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        // Write your solution here
        return new ArrayList<>();
    }
}

#include <vector>
using namespace std;

vector<vector<int>> levelOrder(TreeNode* root) {
    // Write your solution here
    return {};
}

function levelOrder(root) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [[3,9,20,15,7]]Collecting all nodes in one list instead of grouping by levels.✅ Use a queue and process nodes level by level, grouping nodes per level.

Wrong: [[3],[9,20],[15]]Missing right child node 7 in last level due to incorrect child processing.✅ Ensure both left and right children are enqueued if not null.

Wrong: [[1],[2,3,4],[5,6,7]]Incorrect level grouping, mixing nodes from different levels.✅ Process nodes in batches equal to queue size at each level.

Wrong: []Not handling null root input, returning empty or error incorrectly.✅ Add explicit check for null root and return empty list.

Wrong: [[1,2,3,4,5,6,7,8,9,10,...]]Using recursive level collection causing O(n^2) time and TLE on large inputs.✅ Implement BFS with queue for O(n) time complexity.

✓

Test Cases

Try testing your code with empty and single node trees to handle base cases.

Test skewed trees and incomplete levels to catch subtle bugs.

Optimize your BFS implementation to handle large inputs efficiently.

t1_01basic

Input{"root":[3,9,20,null,null,15,7]}

Expected[[3],[9,20],[15,7]]

⏱ Performance - must finish in 2000ms

The root is 3. Level 1 has 3. Level 2 has 9 and 20. Level 3 has 15 and 7.

💡 Think about visiting nodes level by level using a queue.

💡 Use a BFS approach: enqueue root, then enqueue children level-wise.

💡 Collect nodes at each level before moving to the next.

Why it failed: Output differs from expected level order traversal; likely BFS queue logic error. Fix by ensuring nodes are grouped by levels using queue size at each iteration.

✓ Correct BFS level order traversal implemented.

t1_02basic

Input{"root":[1,2,3,4,5,6,7]}

Expected[[1],[2,3],[4,5,6,7]]

⏱ Performance - must finish in 2000ms

Complete binary tree with root 1, next level 2 and 3, last level 4,5,6,7.

💡 Use a queue to process nodes level by level.

💡 At each level, process all nodes currently in the queue before adding their children.

💡 Return a list of lists where each inner list contains nodes of one level.

Why it failed: Incorrect grouping of nodes by level; possibly mixing nodes from different levels. Fix by processing nodes in batches equal to current queue size.

✓ Correctly groups nodes by level using BFS.

t2_01edge

Input{"root":null}

Expected[]

⏱ Performance - must finish in 2000ms

Empty tree returns empty list.

💡 Check if root is null before processing.

💡 Return empty list immediately if tree is empty.

💡 Avoid processing when root is null to prevent errors.

Why it failed: Function does not handle null root; returns non-empty or errors. Fix by adding null root check and returning [].

✓ Correctly returns empty list for empty tree.

t2_02edge

Input{"root":[42]}

Expected[[42]]

⏱ Performance - must finish in 2000ms

Single node tree returns list with one list containing root value.

💡 A single node forms one level by itself.

💡 Ensure the function handles trees with only one node.

💡 Return [[root.val]] when no children exist.

Why it failed: Fails single node case; may return empty or incorrect structure. Fix by handling single node as one level list.

✓ Correctly returns single level list for single node tree.

t2_03edge

Input{"root":[1,2,null,3,null,4,null,5]}

Expected[[1],[2],[3],[4],[5]]

⏱ Performance - must finish in 2000ms

Tree with only left children, each level has one node.

💡 Traverse level by level even if only one child per node.

💡 Queue will have one node per level in this case.

💡 Ensure no assumptions about multiple children per node.

Why it failed: Fails skewed left tree; may skip levels or group incorrectly. Fix by processing each node's children properly even if one child is null.

✓ Correctly handles skewed left child tree.

t3_01corner

Input{"root":[1,null,2,null,3,null,4]}

Expected[[1],[2],[3],[4]]

⏱ Performance - must finish in 2000ms

Tree with only right children, each level has one node.

💡 Check that your code does not assume left child exists.

💡 Process right children similarly to left children.

💡 Ensure queue adds right child nodes correctly.

Why it failed: Fails skewed right tree; may ignore right children. Fix by adding right child to queue if not null.

✓ Correctly handles skewed right child tree.

t3_02corner

Input{"root":[1,2,3,4,5,null,null,6,null,null,null]}

Expected[[1],[2,3],[4,5],[6]]

⏱ Performance - must finish in 2000ms

Tree with missing nodes at some levels, tests correct level grouping.

💡 Do not assume complete binary tree structure.

💡 Process null children correctly by skipping them.

💡 Ensure levels are grouped by actual nodes present.

Why it failed: Incorrect level grouping due to null children handling. Fix by skipping null children and grouping nodes by actual presence.

✓ Correctly groups nodes by level with missing children.

t3_03corner

Input{"root":[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]}

Expected[[1],[2,3],[4,5,6,7],[8,9,10,11,12,13,14,15]]

⏱ Performance - must finish in 2000ms

Perfect binary tree of height 4, tests correct BFS level grouping.

💡 Use queue size to separate levels.

💡 Process all nodes at current level before next.

💡 Ensure no nodes from next level are mixed in current level.

Why it failed: Mixing nodes from different levels in output. Fix by processing nodes in batches equal to queue size per level.

✓ Correctly separates nodes by level in perfect binary tree.

t4_01performance

Input{"root":[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100]}

Expectednull

⏱ Performance - must finish in 2000ms

Large tree with 100 nodes, BFS O(n) must complete within 2 seconds.

💡 Use BFS with queue for O(n) time complexity.

💡 Avoid recursive solutions with O(n^2) complexity.

💡 Process nodes level by level efficiently.

Why it failed: TLE due to inefficient O(n^2) or recursive approach. Fix by implementing BFS with queue for O(n) traversal.

✓ Efficient BFS traversal confirmed with O(n) complexity.

Practice

1. Consider the following Python code for N-ary tree level order traversal. Given the tree root = Node(1, [Node(3, [Node(5), Node(6)]), Node(2), Node(4)]), what is the value of res after the first iteration of the outer while loop completes?

easy

A. [[1]]

B. [[1, 3, 2, 4]]

C. [[3, 2, 4]]

D. [[5, 6]]

Solution

1. Step 1: Trace the first outer loop iteration

   Initially, current_level contains only the root node with value 1.

2. Step 2: Collect values and enqueue children

   We pop node 1, append its value to level_nodes -> [1], and enqueue its children (3, 2, 4) into next_level.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   After first iteration, res = [[1]] as only root level processed [OK]

Hint: First level contains only root node value [OK]

Common Mistakes:

• Confusing first level with all children nodes

2. The following code attempts the optimal DFS approach for bottom-up level order traversal. Identify the line containing the subtle bug that causes incorrect output for an empty tree input.

def levelOrderBottom(root):
    levels = []
    def dfs(node, level):
        if not node:
            return
        if len(levels) == level:
            levels.append([])
        levels[level].append(node.val)
        dfs(node.left, level + 1)
        dfs(node.right, level + 1)
    dfs(root, 0)
    return levels[::-1]

medium

A. Line 10: dfs(root, 0)

B. Line 11: return levels[::-1]

C. Line 2: levels = []

D. Line 3: def dfs(node, level):

Solution

1. Step 1: Consider empty tree input (root = None)

   If root is None, dfs returns immediately without adding levels.

2. Step 2: Check what happens after dfs call

   levels remains empty, so return levels[::-1] returns [], which is correct and expected.

3. Step 3: Identify bug

   Returning levels[::-1] when levels is empty is correct; the subtle bug is missing an explicit check for root being None before calling dfs to avoid unnecessary calls.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Returning reversed empty list is correct; no bug in dfs call line [OK]

Hint: Returning reversed empty list is safe for empty tree [OK]

Common Mistakes:

• Assuming dfs call on None causes error
• Not handling empty tree explicitly but no failure occurs

3. What is the time complexity of the optimal BFS with column tracking and ordered map approach for vertical order traversal of a binary tree with n nodes and k distinct columns?

medium

A. O(n log n)

B. O(n)

C. O(n log k)

D. O(k log n)

Solution

1. Step 1: Identify main operations

   Each node is processed once (O(n)). For each node, insertion into ordered map (SortedDict) costs O(log k) where k is number of columns.

2. Step 2: Combine complexities

   Total time is O(n) * O(log k) = O(n log k). Sorting all nodes (O(n log n)) is avoided here.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Ordered map insertion dominates, giving O(n log k) [OK]

Hint: Ordered map insertion per node costs log k, not log n [OK]

Common Mistakes:

• Assuming O(n) ignoring map insertion cost
• Confusing k (columns) with n (nodes) in complexity

4. What is the time complexity of the iterative DFS solution that uses a stack to count good nodes in a binary tree with n nodes and height h?

medium

A. O(n log n) due to repeated max value comparisons

B. O(nh) because max value must be tracked along paths of length h

C. O(n) because each node is visited once and max value updates are O(1)

D. O(h) since only the height of the tree affects traversal

Solution

1. Step 1: Identify number of node visits

   Each node is pushed and popped exactly once from the stack, so O(n) visits.

2. Step 2: Analyze max value update cost

   Updating max_val is a constant time operation per node, no extra traversal per node.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Linear traversal with constant work per node [OK]

Hint: Each node processed once, max_val update O(1) [OK]

Common Mistakes:

• Assuming max_val tracking adds O(h) per node
• Confusing recursion stack space with time
• Thinking max_val comparisons cause O(n log n)

5. Consider the following buggy code snippet for connecting next right pointers in a perfect binary tree. Which line contains the subtle bug that can cause incorrect next pointer connections?

medium

A. Line: head.left.next = head.right

B. Line: if head.next:

C. Line: leftmost = leftmost.left

D. Line: head.right.next = head.next.right

Solution

1. Step 1: Compare the buggy line with the correct logic

   The correct connection is head.right.next = head.next.left, but here it uses head.next.right, which is incorrect.

2. Step 2: Understand the impact

   This causes right child's next pointer to point to the wrong node, breaking the chain.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Right child's next must connect to next node's left child [OK]

Hint: Right child's next points to next node's left child [OK]

Common Mistakes:

• Confusing next.left and next.right
• Skipping null checks
• Not updating leftmost pointer