Solution: Binary Tree Level Order Traversal

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.

---

Leetcode Problem #102 (Medium): Binary Tree Level Order Traversal

---

Description:

(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

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

---

Examples:

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

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

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

---

Constraints:

• The number of nodes in the tree is in the range [0, 2000].
• -1000 <= Node.val <= 1000

---

Idea:

(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

A binary tree level order traversal generally recommends a breadth first search (BFS) approach with the use of a queue data structure. When we process a node (curr), we'll push the node's children onto the end of the queue in the order in which we want to traverse (in this case, left to right). In this way, we'll have finished putting the next row in the queue at the same time we finish iterating through this row.

To help us keep track of the rows, we just nest the main loop inside another loop. At the beginning of the outer loop, we capture the queue length, which will tell us how long the row is. Then we can iterate through that many nodes, popping them off the queue's front one at a time, then process any end-of-row instructions. In the case of this problem, that will mean pushing the current row array (row) onto our answer array (ans).

We'll continue this process until the queue is empty, at which point we will have reached the end of the binary tree, and can return ans.

• Time Complexity: O(N) where N is the number of nodes in the binary tree
• Space Complexity: O(N) for our answer array

---

Javascript Code:

(Jump to: Problem Description || Solution Idea)

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
};

---

Python Code:

(Jump to: Problem Description || Solution Idea)

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        queue, ans = deque([root] if root else []), []
        while len(queue):
            qlen, row = len(queue), []
            for _ in range(qlen):
                curr = queue.popleft()
                row.append(curr.val)
                if curr.left: queue.append(curr.left)
                if curr.right: queue.append(curr.right)
            ans.append(row)
        return ans

---

Java Code:

(Jump to: Problem Description || Solution Idea)

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null) return ans;
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int qlen = queue.size();
            List<Integer> row = new ArrayList<>();
            for (int i = 0; i < qlen; i++) {
                TreeNode curr = queue.poll();
                row.add(curr.val);
                if (curr.left != null) queue.add(curr.left);
                if (curr.right != null) queue.add(curr.right);
            }
            ans.add(row);
        }
        return ans;
    }
}

---

C++ Code:

(Jump to: Problem Description || Solution Idea)

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        if (!root) return ans;
        deque<TreeNode*> queue;
        queue.push_back(root);
        while (!queue.empty()) {
            int qlen = queue.size();
            vector<int> row;
            for (int i = 0; i < qlen; i++) {
                TreeNode* curr = queue.front();
                queue.pop_front();
                row.push_back(curr->val);
                if (curr->left) queue.push_back(curr->left);
                if (curr->right) queue.push_back(curr->right);
            }
            ans.push_back(row);
        }
        return ans;
    }
};

Comments

[advaitkr]

why you have used q[0] and why not q.length.