Last updated on January 5th, 2025 at 12:55 am

Here, we see a Binary Tree Level Order Traversal LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Breadth First Search, Tree

Companies

Amazon, Apple, Bloomberg, Facebook, LinkedIn, Microsoft

Level of Question

Medium

Binary Tree Level Order Traversal LeetCode Solution

1. Problem Statement

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

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]

Example 2:
Input: root = [1]
Output: [[1]]

Example 3:
Input: root = []
Output: []

2. Coding Pattern Used in Solution

The coding pattern used in all the provided implementations is Tree Breadth-First Search (BFS). This pattern commonly traverses a tree level by level, processing all nodes at the current depth before moving to the next depth. BFS is implemented using a queue data structure to keep track of nodes at each level.

3. Code Implementation in Different Languages

3.1 Binary Tree Level Order Traversal C++

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

3.2 Binary Tree Level Order Traversal Java

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) 
    {
        List<List<Integer>>al=new ArrayList<>();
        pre(root,0,al);
        return al;
    }
    public static void pre(TreeNode root,int l,List<List<Integer>>al)
    {
        if(root==null)
            return;
        if(al.size()==l)
        {
            List<Integer>li=new ArrayList<>();
            li.add(root.val);
            al.add(li);
        }
        else
            al.get(l).add(root.val);
        pre(root.left,l+1,al);
        pre(root.right,l+1,al);
    } 
}

3.3 Binary Tree Level Order Traversal JavaScript

var levelOrder = function(root) {
    let q = [root], ans = []
    while (q[0]) {
        let qlen = q.length, row = []
        for (let i = 0; i < qlen; i++) {
            let curr = q.shift()
            row.push(curr.val)
            if (curr.left) q.push(curr.left)
            if (curr.right) q.push(curr.right)
        }
        ans.push(row)            
    }
    return ans
};

3.4 Binary Tree Level Order Traversal Python

class Solution(object):
    def levelOrder(self, root):
        if not root:
            return []
        Q = deque([root])
        levels = [[root.val]]
        temp = deque()
        while Q:
            node = Q.popleft()
            if node.left: temp.append(node.left)
            if node.right: temp.append(node.right)
            if not Q:
                if temp:
                    levels.append([n.val for n in temp])
                Q = temp
                temp = deque()
        return levels

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(N)	O(W)
Java	O(N)	O(W)
JavaScript	O(N)	O(W)
Python	O(N)	O(W)

• The Time complexity is O(N) because each node is visited once.
• The Space complexity is O(W) because the queue (or recursion stack) holds up to the maximum number of nodes at any level.