Binary Tree Level Order Traversal using Javascript

Question

This is a leetcode question.

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example: Given binary tree [3, 9, 20, null, null, 15, 7],
    3
   / \
  9  20
    /  \
   15   7
return its level order traversal as:
[
  [3],
  [9,20],
  [15,7]
]

But i am trying it a new way in JavaScript and not going entirely by their solution. So far i am able to print the arrays but

How can different levels be printed in new rows

Below is my code so far:

var levelOrder = function(root) {
let output = [];
let queue = [];
let currentNode = root;
queue.push(currentNode);
let currentLevel = 1;
while(queue.length){
    
    currentNode = queue.shift();
    currentLevel--; //this will ensure we are adding new lines only on next level
    output.push(currentNode);
    
    if(currentNode.left){
        queue.push(currentNode.left);
    }
    if(currentNode.right){
        queue.push(currentNode.right);
    }
    
    if(currentLevel = 0){
        output = output + '/n'; //Insert a new line
        currentLevel = queue.length; //2
    }
}
return output;
};

Input: [3,9,20,null,null,15,7],

Expected Output:
[
[3],
[9,20],
[15,7]
]

LeetCode Question Link: BinaryTreeTraversalUsingBFS

Strategy you are looking for is BFS, refer these links - npmjs.com/package/@dsinjs/binary-tree and dsinjs.github.io/binary-tree/#findbfs — Siddhesh Kulkarni
– Siddhesh Kulkarni, Commented Nov 29, 2020 at 19:28

blex · Accepted Answer · 2020-07-07 23:09:11Z

9

I think you're almost there. Not sure what output = output + '/n'; is for though.

This'd pass through:

var levelOrder = function(root) {
    const levels = []

    if(!root) {
        return levels
    }

    const queue = [root]
    while (queue.length){
       const queueLength = queue.length
       const level = []

       for(let i = 0; i < queueLength; i++){

           const node = queue.shift()

           if(node.left){
               queue.push(node.left)
           }
           if(node.right){
               queue.push(node.right)
           }

           level.push(node.val)
       }
       levels.push(level)
   }
    return levels
}

References

For additional details, you can see the Discussion Board. There are plenty of accepted solutions with a variety of languages and explanations, efficient algorithms, as well as asymptotic time/space complexity analysis^{1, 2} in there.

edited Jul 7, 2020 at 23:09

blex

25.7k6 gold badges48 silver badges78 bronze badges

answered Jul 7, 2020 at 23:03

Emma Marcier

27.8k12 gold badges49 silver badges71 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

winterishere Over a year ago

That;s a great solution you hit the bulls eye. I am new to Javascript, so basically you have level array and you are pushing this array to parent array-levels each time child nodes are complete. New line doesn't matter here for arrays it's just for the display, but i suppose if we need to show it as a string then new line has to be entered. Thank you.

Alvin · Accepted Answer · 2020-07-07 23:18:16Z

2

Base on your codebase, I modify it for work.

Add an index for increasing the output index.
Use strict equality operator instead of assignment variable.
Remove output = output + '/n', because output is an array.

var levelOrder = function (root) {
  let output = [];
  let queue = [];
  let currentNode = root;
  queue.push(currentNode);
  let currentLevel = 1;
  let index = 0; // Add an index for increasing the output index

  while (queue.length) {

    currentNode = queue.shift();
    currentLevel--;

    if (!output[index]) { // Set default is an array for each output element in first time
      output[index] = [];
    }

    output[index].push(currentNode.val);

    if (currentNode.left) {
      queue.push(currentNode.left);
    }

    if (currentNode.right) {
      queue.push(currentNode.right);
    }

    if (currentLevel === 0) { // Use strict equality operator to compare 0
      index++; // increase index
      currentLevel = queue.length;
    }
  }

  return output;
};

edited Jul 7, 2020 at 23:18

answered Jul 7, 2020 at 23:11

Alvin

4943 silver badges7 bronze badges

1 Comment

Foysal Ahmed Emon Over a year ago

I think your code will not work for this input : Input [1,2,3,4,null,null,5] stdout 1 [ [ 1 ], [ 2, 3 ], [ 4 ], [ 5 ] ] Output [[1],[2,3],[4],[5]] Expected [[1],[2,3],[4,5]]

Ahmad Atrach · Accepted Answer · 2021-08-29 12:58:52Z

0

This is the recursion solution to it

    var levelOrder = function(root) {
    let result =[];
    if(!root)return result;
    if(!root.left && !root.right){
        result.push([root.val]);
        return result;
    }
    const pushIntoResult =(node, level) =>{
        if(!node) return;
        if(!result[level]){
            result.push([]);
        }
        result[level].push(node.val);
        pushIntoResult(node.left, level+1);
        pushIntoResult(node.right, level+1);
    }
    pushIntoResult(root, 0);
    return result;
};

answered Aug 29, 2021 at 12:58

Ahmad Atrach

1

Comments

sunit shakya · Accepted Answer · 2022-01-24 07:23:24Z

0

You may try this bit modification in @Ahmad Atrach' code

const dfs = (node,result,level) => {

if(!node) return;
if(!result[level]){
    result.push([]);
}
result[level].push(node.val);
dfs(node.left,result, level+1);
dfs(node.right,result, level+1);
}
var levelOrder = function(root) {

  if(!root) return [];
  let result = [];
  dfs(root,result,0);

  return result;
};

answered Jan 24, 2022 at 7:23

sunit shakya

516 bronze badges

Collectives™ on Stack Overflow

Binary Tree Level Order Traversal using Javascript

4 Answers 4

References

1 Comment

1 Comment

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

References

1 Comment

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related