Posts Binary Tree - Level Order Traversal II
Post
Cancel

Binary Tree - Level Order Traversal II

PROBLEM DESCRIPTION

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). Leetcode

SOLUTION

For the main explaination, see: BST Level Order Traversal

This query needs some tweaking, because we need to return the levels as a List<List>. So, after every level, we need a way to create a new List to add to our response.

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
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        
        //If the BST is null
        if(root == null) return new ArrayList<List<Integer>>();
        
        //We will make the Queue type as TreeNode because we need to access the left and right children later
        Queue<TreeNode> q = new LinkedList<>();

        //Initialize the queue with the root node and NULL
        //The idea is to add NULL after every level
        //While removing elements from the queue, if we encounter a NULL, that means that we have covered a certain level
        //So we can append the current list to the answer and continue
        q.add(root);
        q.add(null);
        
        //To store final answer
        List<List<Integer>> res = new ArrayList<>();

        //To store each level
        List<Integer> temp = new ArrayList<>();
        
        //If there is one node and NULL, size must be at least 1
        while(q.size() > 1){

            //Remove the element from the queue
            TreeNode f = q.remove();

            //If the element is NULL, that means, we have completed a level. 
            if(f == null){
                //Add NULL to end of the queue so mark the next level because at this moment, we must have completed adding all childer of the current level
                q.add(null);
                //Add current level to answer
                res.add(temp);
                //Reset array so store next level
                temp = new ArrayList<>();
            }else{
                //Else, add the current element to current level
                temp.add(f.val);
                //Add childer to the queue
                if(f.left != null) q.add(f.left);
                if(f.right != null) q.add(f.right);
            }
        }
        
        //Add final level
        res.add(temp);
        
        return res;
        
    }
}
This post is licensed under CC BY 4.0 by the author.