DEV Community

loading...

102. Binary Tree Level Order Traversal (javascript solution)

cod3pineapple profile image codingpineapple ・1 min read

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

Solution:

Time Complexity : O(n)
Space Complexity: O(n)

// BFS
var levelOrder = function(root) {
    if(!root) return []
    const queue = []
    const output = []
    queue.push(root)
    while(queue.length) {
        // Remove all the current nodes in the queue and add each node's children to the queue
        const len = queue.length
        const row = []
        for(let i = 0; i < len; i++) {
            const cur = queue.shift()
            if(cur.left) queue.push(cur.left)
            if(cur.right) queue.push(cur.right)
            // Push the current node val to the row array
            row.push(cur.val)
        }
        // Push the current row array into the output array
        output.push(row)
    }
    return output
};
Enter fullscreen mode Exit fullscreen mode

Discussion (0)

Forem Open with the Forem app