102. Binary Tree Level Order Traversal

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

 

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: []

 

Constraints:

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

Approach) BFS

We can use BFS to traverse the tree and collect all the nodes for a given level in a currentLevel array. We can store each of our currentLevel arrays in an results array. Once we finish our traversal our solution should be contained in results.

If your not familiar with how to implement BFS, continue to read on here. We’ll describe BFS implementation as it relates to this problem. If you are familiar feel free to skip.

• If there is no root, return []
• Initialize a queue with the root node
• Initialize a results array
• While the queue is not empty
• Initialize a currentLevel array
• Capture the currentLength of the queue
• Declare a for loop, and iterate through the queue from 0 to the currentLength
• Shift() from the queue
• If node.left, push node.left to the queue
• If node.right, push node.right to the queue
• push node.val to the currentLevel
• push currentLevel to results
• Return results

Code:

const levelOrder = (root) => {

    if (!root) return []

    const results = [];
    const queue = [root];

    while (queue.length > 0) {
        const currentLength = queue.length;
        const currentLevel = [];

        for(let i = 0; i < currentLength; i++) {
            const node = queue.shift();
            if (node.left) {
                queue.push(node.left);
            }
            if (node.right) {
                queue.push(node.right);
            }
            currentLevel.push(node.val);
        }

        results.push(currentLevel);
    }

    return results;
}

Complexity analysis.

Time Complexity

    We are traversing through the complete tree which needs O(N).

Space Complexity

   space complexity is O(N) + O(K). where K is the level with the most nodes

Conclusion

That’s all folks! In this post, we solved LeetCode problem #102. Binary Tree Level Order Traversal

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!