Skip to content

116. Populating Next Right Pointers in Each Node 👍

Approach 1: Recursive

  • Time: $O(n)$
  • Space: $O(h)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
 public:
  Node* connect(Node* root) {
    if (root == nullptr)
      return nullptr;
    connectTwoNodes(root->left, root->right);
    return root;
  }

 private:
  void connectTwoNodes(Node* p, Node* q) {
    if (p == nullptr)
      return;
    p->next = q;
    connectTwoNodes(p->left, p->right);
    connectTwoNodes(q->left, q->right);
    connectTwoNodes(p->right, q->left);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
  public Node connect(Node root) {
    if (root == null)
      return null;
    connectTwoNodes(root.left, root.right);
    return root;
  }

  private void connectTwoNodes(Node p, Node q) {
    if (p == null)
      return;
    p.next = q;
    connectTwoNodes(p.left, p.right);
    connectTwoNodes(q.left, q.right);
    connectTwoNodes(p.right, q.left);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
  def connect(self, root: 'Node | None') -> 'Node | None':
    if not root:
      return None

    def connectTwoNodes(p, q) -> None:
      if not p:
        return
      p.next = q
      connectTwoNodes(p.left, p.right)
      connectTwoNodes(q.left, q.right)
      connectTwoNodes(p.right, q.left)

    connectTwoNodes(root.left, root.right)
    return root

Approach 2: Iterative

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
 public:
  Node* connect(Node* root) {
    Node* node = root;  // the node that is above the current needling

    while (node && node->left) {
      Node dummy(0);  // the dummy node before needling
      // Needle the children of the node.
      for (Node* needle = &dummy; node; node = node->next) {
        needle->next = node->left;
        needle = needle->next;
        needle->next = node->right;
        needle = needle->next;
      }
      node = dummy.next;  // Move the node to the next level.
    }

    return root;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
  public Node connect(Node root) {
    Node node = root; // the node that is above the current needling

    while (node != null && node.left != null) {
      Node dummy = new Node(); // a dummy node before needling
      // Needle the children of the node.
      for (Node needle = dummy; node != null; node = node.next) {
        needle.next = node.left;
        needle = needle.next;
        needle.next = node.right;
        needle = needle.next;
      }
      node = dummy.next; // Move the node to the next level.
    }

    return root;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
  def connect(self, root: 'Node') -> 'Node':
    node = root  # the node that is above the current needling

    while node and node.left:
      dummy = Node(0)  # a dummy node before needling
      # Needle the children of the node.
      needle = dummy
      while node:
        needle.next = node.left
        needle = needle.next
        needle.next = node.right
        needle = needle.next
        node = node.next
      node = dummy.next  # Move the node to the next level.

    return root