1. Introduction

Given the root of a binary tree, return the binary tree level order traversal of its nodes’ values. (i.e., from left to right, level by level).

This article is part of Binary Tree-Traversals. Read more about Binary Tree traversals here.

2. Content

Binary Tree’s level order traversal or Breadth First Search(BFS) uses Queue data structure. And for Depth First Search(DFS), we use Stack data structure.

Level Order Traversal: [[50],[30,40],[10,12,45,56],[89,48]]

3. Level Order Traversal

The idea behind BFS or level order traversal is that we explore all nodes at current depth and then move to the next depth level.Extra memory, i.e. Queue is used to keep track of nodes that are not yet explored.

1. If the root is null, return the empty List. No need to explore any further.

if(root == null) return Collections.emptyList();

2. Initialize the result.

List<List<Integer>> result = new ArrayList<>();

3. Initialize the Queue data structure to hold the nodes that need to be explored. Add root node to it.

Deque<TreeNode> q = new ArrayDeque<>();
q.add(root);

4. While the Queue isn’t empty, traverse the nodes from the Queue. Once traversed, insert the next level into the Queue so those nodes will be explored next.

while(!q.isEmpty()) {
    int size = q.size();
    List<Integer> list = new ArrayList<>();
    // Explore all nodes at current level
    for(int i = 0; i < size; i++) {
        TreeNode curr = q.poll();
        list.add(curr.val);
        // Insert nodes in Queue for next level 
        // so they will be explored later.
        if(curr.left != null) q.add(curr.left);
        if(curr.right != null) q.add(curr.right);
    }
    result.add(list);
}

Entire implementation:

    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) return Collections.emptyList();

        List<List<Integer>> result = new ArrayList<>();

        Deque<TreeNode> q = new ArrayDeque<>();
        q.add(root);

        while (!q.isEmpty()) {
            int size = q.size();
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode curr = q.poll();
                list.add(curr.val);
                if (curr.left != null) q.add(curr.left);
                if (curr.right != null) q.add(curr.right);
            }
            result.add(list);
        }
        return result;
    }

Time Complexity:

1. O(n) where n is the total number of nodes in a tree. We explore every node, hence the time complexity is O(n).

Space Complexity:

1. O(n) where n is the total number of nodes in a tree. We save every node in result List, hence the space complexity is O(n).

4. Conclusion

In this article, we saw how to implement Breadth first search or BFS, i.e. level order traversal of a Binary Tree.

GitHub link: https://github.com/savanibharat/justamonad-tutorials/blob/master/justamonad-tutorials-leetcode/src/main/java/com/justamonad/tutorials/leetcode/tree/BSTLevelOrderTraversal.java