Populating Next Right Pointers in Each Node Medium 0 attempts
LeetCode ↗

Populating Next Right Pointers in Each Node

Medium TreeBinary TreeDFS LeetCode

You're given a perfect binary tree, where each node has a next pointer in addition to its left and right children. Fill in every node's next pointer so it points to the node immediately to its right on the same level, or to null if it's the rightmost node on that level.

Input Format
Implement connect(root). Inputs below show JavaScript function arguments; there is no stdin parsing. Trees use level-order arrays with null for missing children. The editor passes nodes with val, left, and right properties; [] becomes null.
Output Format
Return the result described in the statement. The output lists the values reached through next pointers at each level.

Sample Input and Output

Example 1 ยท Run Sample

Input
root = [1,2,3,4,5,6,7]
Output
[[1],[2,3],[4,5,6,7]]

Example 2

Input
root = []
Output
[]
Constraints
  • 0 <= number of nodes <= 2^12 - 1
  • -1000 <= Node.val <= 1000
Test Cases (2)
Case 1
Args: [[1,2,3,4,5,6,7]] Expected: [[1],[2,3],[4,5,6,7]]
Case 2
Args: [[]] Expected: []
Topics
TreeBinary TreeDFS

Level-by-Level Using Next Pointers

javascript
function connect(root) {
  if (!root) return root;
  let leftmost = root;
  while (leftmost.left) {
    let curr = leftmost;
    while (curr) {
      curr.left.next = curr.right;
      if (curr.next) curr.right.next = curr.next.left;
      curr = curr.next;
    }
    leftmost = leftmost.left;
  }
  return root;
}

Time: O(n) | Space: O(1)

Saved in this browser only. Private to you.

JavaScript