LeetCode: Populating Next Right Pointers in Each Node Solution

Approach: BFS

Breadth-first traversal

Grab all nodes with the same level and work on them

Implementation

1var connect = function (root) {
2  if (!root) return null
3
4  let queue = []
5  let accLevel = 0
6
7  const addLevel = (node, level = 0) => {
8    if (!node) return
9    node.level = level
10    addLevel(node.left, level + 1)
11    addLevel(node.right, level + 1)
12  }
13
14  addLevel(root)
15
16  queue.push(root)
17
18  while (queue.length > 0) {
19    const nodes = []
20
21    while (queue.length > 0 && queue[0].level === accLevel) {
22      nodes.push(queue.shift())
23    }
24
25    for (let i = 0; i < nodes.length; i++) {
26      nodes[i].next = nodes[i + 1] || null
27      if (nodes[i].left) {
28        queue.push(nodes[i].left, nodes[i].right)
29      }
30    }
31
32    accLevel++
33  }
34
35  return root
36}

Approach: Recursive

The most important part is to connect next of 2 subtrees

Implementation

1var connect = function (root) {
2  if (!root) return null
3  if (!root.left) return root
4
5  root.left.next = root.right
6  if (root.next) {
7    root.right.next = root.next.left
8  }
9  connect(root.left)
10  connect(root.right)
11
12  return root
13}