Binary Tree Level Order Traversal

Problem Statement

LeetCode-102: 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).

Approach

There are two ways to solve this problem. Let us first discuss the Breadth First Search (BFS) approach:

1. Use a Queue to store the nodes of the tree.
2. Start by initializing the queue with the root node.
3. For each level (denoted by the queue size at the start of the loop), pop the nodes from the queue.
4. Add the value of the node to the current level.
5. If the node has non-null left and right children, add them to the queue.
6. Repeat the process until the queue is empty.
7. Return the result.

We can also solve this problem using a Depth First Search (DFS) recursive approach:

1. Initialize result list (List<List<Integer>>) to store the node values at each level.
2. Use a new method to traverse the tree that accepts the current node and the level.
3. If the current level is equal to the size of the result, this means we have reached a new level which has not been iterated before. Create a new list for this level.
4. Add the value of the current node to the list of the current level.
5. If the current node has non-null left and right children, recursively call the method with the left and right children and the level incremented by 1.
6. Return the result.

Implementation

Let us first implement the BFS approach:

public List<List<Integer>> levelOrder(TreeNode root) {
    Queue<TreeNode> queue = new LinkedList<>();
    List<List<Integer>> result = new ArrayList<>();
    
    // handle the empty tree case
    if(null != root){
        queue.add(root);
    }
    
    while(!queue.isEmpty()){
        int nodesAtCurrentLevel = queue.size();
        List<Integer> nodeValues = new ArrayList<>();

        while(nodesAtCurrentLevel > 0){
            TreeNode node = queue.remove();
            nodeValues.add(node.val);
            nodesAtCurrentLevel--;
            
            if(null != node.left){
                queue.add(node.left);
            }
            if(null != node.right){
                queue.add(node.right);
            }
        }
        result.add(nodeValues);
    }
    return result;
}

Now, let us implement the DFS approach:

private final List<List<Integer>> nodesAtLevel = new ArrayList<>();

public List<List<Integer>> levelOrder(TreeNode root) {
    if(null == root){
        return nodesAtLevel;
    }
    traverse(root, 0);
    return nodesAtLevel;
}

private void traverse(TreeNode node, int level){
    if(nodesAtLevel.size() == level){
        nodesAtLevel.add(level, new ArrayList<>());
    }

    List<Integer> nodeValues = nodesAtLevel.get(level);
    nodeValues.add(node.val);
    
    if(null != node.left){
        traverse(node.left, level+1);
    }
    if(null != node.right){
        traverse(node.right, level+1);
    }
}

Complexity Analysis

Assuming $N$ is the number of nodes in the binary tree and $H$ is the height of the binary tree:

• Both the BFS and DFS approaches have the same time complexity of $O(N)$, as we visit each node exactly once
• The space complexity of the BFS approach is $O(N)$,as we are using a queue to store the nodes of the tree.
• On the other hand, the space complexity of the DFS approach is $O(H)$ due to the associated recursive call stack.