Binary Tree Level Order Traversal

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

Intuition

DFS

We use layer to track current node’s depth. We insert values from top to bottom and from left to right by visiting left subtree before right subtree.

BFS

We use a queue to track all nodes at the current level. For each level, we process all nodes in the queue: extract their values and add their children to the queue for the next level.

Algorithm

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        trace(root, ans, 0);
        return ans;
    }
    void trace(TreeNode* root, vector<vector<int>>& ans, int layer){
        if(root == nullptr){
            return;
        }
        if(layer >= ans.size()){
            ans.push_back(vector<int>());
        }
    
        ans[layer].push_back(root->val);

        trace(root->left, ans, layer+1);
        trace(root->right, ans, layer+1);
    }
};

BFS

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
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        if(root == nullptr) return ans; 
        queue<TreeNode*> q;
        
        q.push(root);
        
        while(!q.empty()){
	        int size = q.size();
	        vector<int> level;
	        
	        for(int i = 0; i < size; i++){
		        TreeNode* node = q.front();
		        q.pop();
		        
		        level.push_back(node->val);
                if(node->left){
		        q.push(node->left);
                }
                if(node->right){
		        q.push(node->right);
                }
			}
			
			ans.push_back(level);
        }
        return ans;
    }
};