Populating Next Right Pointers in Each Node

Patrick Leaton

Published: July 28, 2021, 8 p.m.

Problem Description

You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Follow up:

You may only use constant extra space.
Recursive approach is fine, you may assume implicit stack space does not count as extra space for this problem.

Example 1:

Input: root = [1,2,3,4,5,6,7]
Output: [1,#,2,3,#,4,5,6,7,#]
Explanation: Given the above perfect binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.

Constraints:

The number of nodes in the given tree is less than 4096.
-1000 <= node.val <= 1000

The description was taken from https://leetcode.com/problems/populating-next-right-pointers-in-each-node/.

Problem Solution

#Iterative BFS

#O(N) Time, O(N) Recursive Space, O(1) Additional Space

class Solution:

def connect(self, root: 'Node') -> 'Node':

if not root:

return None

level = root

while level.left:

node = level

while node:

node.left.next = node.right

if node.next:

node.right.next = node.next.left

node = node.next

level = level.left

return root

#Recursive DFS

#O(N) Time, O(N) Recursive Space, O(1) Additional Space

class Solution:

def connect(self, root: 'Node') -> 'Node':

if not root:

return None

if root.left:

root.left.next = root.right

if root.next:

root.right.next = root.next.left

self.connect(root.left)

self.connect(root.right)

return root

Problem Explanation

Iterative Breadth-First Search

Since we are setting next attributes of nodes to other nodes on the same level, the most straightforward way to solve this problem may be with a Breadth-First Search. However, we actually don't need to keep a queue for traversing the levels, we can just iteratively keep stepping down the left branch of the tree.

First off, if we have no root then we have no next node to connect.

If that is the case, we will return nothing.

if not root:

return None

Otherwise, we will initialize our level at the root.

level = root

While we still have a node to step down and left to, we will continue traversing levels. We will set a node pointer to the leftmost node each time we step down to a new level.

while level.left:

node = level

Then, while the node pointer hasn't reached a null node, we will continue stepping to the right through nodes in the current level.

while node:

At each level, we will be setting next pointers to nodes in the level below us.

The simple pointer we'll set is the left child to the right child.

node.left.next = node.right

The more difficult pointer we'll set is the right child of the current node to the left child of the next node.

In order to do that, we will need to check if we have set a next pointer to the next node on the current level.

If we have, then we have a bridge to get to the next pointer's left child. We can set our current pointer's right child's next pointer to the next node's left child.

if node.next:

node.right.next = node.next.left

After setting these pointers, we will iterate to the next node.

node = node.next

Once the node pointer has hit a null value, we will step down to the leftmost child within the next level.

level = level.left

This will continue until we have no more left children to step down to, in which case we will return the root of the newly connected tree.

return root

Recursive Depth-First Search

We can also solve this problem using a DFS, it is a similar idea as the iterative function, but we will recurse the left child first within each function call so that next nodes are set on the deep-left side of the tree before we start messing with any branches toward the right.

In order to reuse the given function and not have to make a new one, we'll be doing a postorder traversal. Through this traversal, we will be creating these pointers from the bottom up instead of top-down, as we did in the iterative version.

Being a recursive function, let's make sure we set our base case so that this function doesn't run indefinitely.

If we have a null root input, which will happen once we reach the bottom of the left side of the tree, we will return.

if not root:

return None

Same as the iterative version, at each level, we will be setting next pointers to nodes in the level below us.

The simple pointer we'll set is the left child to the right child. In this recursive version, we will need to make sure that the left child exists, because if we are at the bottom level of the tree then we would be trying to connect together two null nodes and would get an error.

if root.left:

root.left.next = root.right

Also, same as the iterative version, the more difficult pointer we'll set is the right child of the current node to the left child of the next node.

In order to do that, we will need to check if we have set a next pointer to the next node on the current level.

If we have, then we have a bridge to get to the next pointer's left child. We can set our current pointer's right child's next pointer to the next node's left child.

if root.next:

root.right.next = root.next.left

Then, we will continue the DFS on left and right children left first.

self.connect(root.left)

self.connect(root.right)

Once the DFS has finished with the left and right children of a given function call, the function will return its current node.

return root