CODEWITHSUNDEEP
javascriptarraysalgorithmtreetraversal
Altaf
Altaf

Reputation: 419

Trying to return a level order traversal of a binary tree

I have the following code that I have worked out on a whiteboard and according to that step through, it gives me the correct result; however, running it on the computer proves otherwise. The code is as follows:

class TreeNode {
    constructor(val) {
        this.val = val
        this.left = this.right = null
    }
}

const levelOrderBottom = root => {
    let visited = []
    if (!root) return visited
    let queue = [root, 's']
    let current
    let row = []

    while (queue.length > 1) {
        current = queue.shift()
        if (current === 's') {
            visited.unshift(row)
            row = []
            queue.push('s')
        } else {
            if (current.left) queue.push(current.left)
            if (current.right) queue.push(current.right)
            row.push(current.val)
        }
    }
    return visited
}

//example 1
const tree1 = new TreeNode(3)
tree1.left = new TreeNode(9)
tree1.right = new TreeNode(20)
tree1.right.left = new TreeNode(15)
tree1.right.right = new TreeNode(7)

console.log(levelOrderBottom(tree1)) //[ [15,7], [9,20], [3] ]

The tree and output should look like the below 

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

However, I get only [ [9,20] ,[3] ]. I am not able to pinpoint the flaw in my logic. Any thoughts, as to what I am doing wrong?

Upvotes: 0

Views: 135

Answers (3)

Matt Timmermans
Matt Timmermans

Reputation: 59144

When you need to separate into levels, you don't need to use a queue:

const levelOrderBottom = root => {
  let visited = []
  let row = root ? [root] : []
  while(row.length > 0) {
    visited.unshift(row.map(n => n.val))
    row = row
      .flatMap(n => [n.left, n.right])
      .filter(n => n!=null);
  }
  return visited
}

Upvotes: 0

Nina Scholz
Nina Scholz

Reputation: 386519

You could store a level and assign to the level.

class TreeNode {
    constructor(val) {
        this.val = val
        this.left = null
        this.right = null
    }
}

const levelOrderBottom = root => {
    let visited = []
    if (!root) return visited
    let queue = [[root, 0]]

    while (queue.length) {
        let [current, level] = queue.shift()
        if (!visited[level]) visited[level] = []
        if (current.left) queue.push([current.left, level + 1])
        if (current.right) queue.push([current.right, level + 1])
        visited[level].push(current.val)
    }
    
    return visited.reverse()
}

//example 1
const tree1 = new TreeNode(3)
tree1.left = new TreeNode(9)
tree1.right = new TreeNode(20)
tree1.right.left = new TreeNode(15)
tree1.right.right = new TreeNode(7)

console.log(levelOrderBottom(tree1)) //[ [15,7], [9,20], [3] ]

Upvotes: 1

Bergi
Bergi

Reputation: 664195

You don't call visited.unshift(row) in the end when queue.length == 1, despite row still containing results you want to add.

Upvotes: 1

Related Questions