Populating Next Right Pointers in Each Node Editorial

Practice Problem Link: Populating Next Right Pointers in Each Node

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

A perfect binary tree is a binary tree in which all interior nodes have two children and all leaves have the same depth or same level.

Given a perfect binary tree which contains an extra next pointer in all the node, populate the next pointers of each node to its next right node.

In nodes with no right nodes, set next to null.

Approach

The idea is to perform a level order traversal and for each node in a level set its next pointer to the next node in the same level.

For the last node in a level, set its next pointer to NULL.

Analysis

• Time Complexity: O(n)
• Auxiliary Space Complexity: O(n)

Implementation

C++

/* This is the Node class definition

class Node {
public:
    Node* left;
    Node* right;
    Node* next;
    int data;

    Node(int data) {
        this->left = NULL;
        this->right = NULL;
        this->next = NULL;
        this->data = data;
    }
};
*/

void connect(Node* root) {
	queue<Node*> treeNodes;
	treeNodes.push(root);
	while (!treeNodes.empty()) {
		int n = treeNodes.size();
		for (int i = 0; i < n; i++) {
			Node* currNode = treeNodes.front();
			treeNodes.pop();
			if (i == n - 1) {
				currNode->next = NULL;
			} else {
				currNode->next = treeNodes.front();
			}
			if (currNode->left != NULL) {
				treeNodes.push(currNode->left);
			}
			if (currNode->right != NULL) {
				treeNodes.push(currNode->right);
			}
		}
	}
	return;
}

Java

/* This is the Node class definition

class Node {
	public Node left;
    public Node right;
    public Node next;
    int data;

    Node(int data) {
        this.data = data;
    }
}
*/

class Solution {
	void connect(Node root) {
    	Queue<Node> treeNodes = new LinkedList<Node> ();
		treeNodes.add(root);
		while (!treeNodes.isEmpty()) {
			int n = treeNodes.size();
			for (int i = 0; i < n; i++) {
				Node currNode = treeNodes.peek();
				treeNodes.poll();
				if (i == n - 1) {
					currNode.next = null;
				} else {
					currNode.next = treeNodes.peek();
				}
				if (currNode.left != null) {
					treeNodes.add(currNode.left);
				}
				if (currNode.right != null) {
					treeNodes.add(currNode.right);
				}
			}
		}
		return;
	}
}

Another Approach

The idea is to perform a level order traversal, but instead of using a queue we will traverse a level with the help of the next pointer of the nodes.

• Initially set the next pointer of root to NULL.
• Now use two nested loop, the outer loop to point to the first node of each level and the inner loop for traversing the level.
• While traversing a level, set the next pointers of the next level. To do that set the next pointer of the left child of a node to its right child (currNode->left->next = currNode->right) and set the next pointer of the right child of a node to the left child of its next node(currNode->right->next = currNode->next->left).

Analysis

• Time Complexity: O(n)
• Auxiliary Space Complexity: O(1)

Implementation

C++

/* This is the Node class definition

class Node {
public:
    Node* left;
    Node* right;
    Node* next;
    int data;

    Node(int data) {
        this->left = NULL;
        this->right = NULL;
        this->next = NULL;
        this->data = data;
    }
};
*/

void connect(Node* root) {
	root->next = NULL;
	while (root != NULL) {
		Node* currNode = root;
		while (currNode != NULL) {
			if (currNode->left != NULL) {
				currNode->left->next = currNode->right;
			}
			if(currNode->right != NULL) {
				if (currNode->next != NULL) {
					currNode->right->next = currNode->next->left;
				} else {
					currNode->right->next = NULL;
				}
			}
			currNode = currNode->next;
		}
		root = root->left;
	}
	return;
}

Java

/* This is the Node class definition

class Node {
	public Node left;
    public Node right;
    public Node next;
    int data;

    Node(int data) {
        this.data = data;
    }
}
*/

class Solution {
	void connect(Node root) {
    	root.next = null;
		while (root != null) {
			Node currNode = root;
			while (currNode != null) {
				if (currNode.left != null) {
					currNode.left.next = currNode.right;
				}
				if(currNode.right != null) {
					if (currNode.next != null) {
						currNode.right.next = currNode.next.left;
					} else {
						currNode.right.next = null;
					}
				}
				currNode = currNode.next;
			}
			root = root.left;
		}
		return;
	}
}