Populate next pointer to inorder successor in Binary Tree

Problem

Given a Binary tree where each node has an extra field (node * next), write a function that puts the inorder successor of that node in the next pointer.

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

Initially, all next pointers have NULL values. Your function should fill these next pointers so that they point to inorder successor.

Examples

Example 1

Solution

This can be petty easily done using the general Inorder traversal algorithm of binary trees. Please refer what is inorder successor or the node here.

Method 1 - Use Reverse Inorder Traversal

We can solve this using a reverse in-order traversal (i.e., right → parent → left) where we keep track of the previously visited node.

We can follow steps:

1. Perform a reverse in-order traversal of the tree.
2. Use a static or member variable to keep track of the previously visited node.
3. During the traversal, update the next pointer of the current node to point to the previously visited node.
4. Move the pointer to the current node.

Code

C

 // Define the node structure
 struct node {
     int val;
     struct node *left;
     struct node *right;
     struct node *next;
 };
 
 // Function to create a new tree node
 struct node* newNode(int val) {
     struct node* node = (struct node*)malloc(sizeof(struct node));
     node->val = val;
     node->left = node->right = node->next = NULL;
     return node;
 }
 
 struct node* prev = NULL; // Pointer to keep track of the previous node in the in-order traversal
 
 // Function to populate the next pointers
 void populateNext(struct node* root) {
     if (root != NULL) {
         populateNext(root->right);
 
         // Set the next pointer of the current node
         root->next = prev;
 
         // Update prev to the current node
         prev = root;
 
         populateNext(root->left);
     }
 }
 
 // Helper function to find the leftmost node
 struct node* leftmost(struct node* root) {
     while (root != NULL && root->left != NULL) {
         root = root->left;
     }
     return root;
 }

 // Function to print the tree nodes along with their next pointers
 void printInOrderWithNext(struct node* root) {
     struct node* current = leftmost(root);
     while (current != NULL) {
         printf("%d ", current->val);
         if (current->next != NULL) {
             printf("-> %d ", current->next->val);
         } else {
             printf("-> NULL ");
         }
         printf("\n");
         current = current->next;
     }
 }
 
 int main() {
     // Create a sample binary tree:
     //      1
     //     / \
     //    2   3
     //   / \
     //  4   5
     struct node* root = newNode(1);
     root->left = newNode(2);
     root->right = newNode(3);
     root->left->left = newNode(4);
     root->left->right = newNode(5);
 
     populateNext(root);
     printInOrderWithNext(root);
 
     // Expected output:
     // 4 -> 2
     // 2 -> 5
     // 5 -> 1
     // 1 -> 3
     // 3 -> NULL
 
     return 0;
 }

Java

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

	Node(int x) {
		val = x;
		left = right = next = null;
	}
}


public class Solution {

	// Member variable to keep track of the previous node in the in-order traversal
	private Node prev = null;

	public void populateNext(Node root) {
		// Perform reverse in-order traversal
		if (root != null) {
			populateNext(root.right);

			// Set the next of the current node
			root.next = prev;

			// Update prev to the current node
			prev = root;

			populateNext(root.left);
		}
	}

	// Helper function to print the tree nodes along with their next pointers
	public void printInOrderWithNext(Node root) {
		Node current = leftmost(root);

		while (current != null) {
			System.out.print(current.val + " ");

			if (current.next != null) {
				System.out.print("-> " + current.next.val + " ");
			} else {
				System.out.print("-> null ");
			}

			System.out.println();
			current = current.next;
		}
	}

	// Helper function to find the leftmost node
	private Node leftmost(Node root) {
		while (root != null && root.left != null) {
			root = root.left;
		}

		return root;
	}

	public static void main(String[] args) {
		Solution solution = new Solution();

		// Create a sample binary tree:
		//      1
		//     / \
		//    2   3
		//   / \
		//  4   5
		Node root = new Node(1);
		root.left = new Node(2);
		root.right = new Node(3);
		root.left.left = new Node(4);
		root.left.right = new Node(5);

		solution.populateNext(root);
		solution.printInOrderWithNext(root);

		// Expected output:
		// 4 -> 2
		// 2 -> 5
		// 5 -> 1
		// 1 -> 3
		// 3 -> null
	}
}

Complexity

• ⏰ Time complexity: O(n), where n is tree size, as we traverse through all nodes in tree.
• 🧺 Space complexity: O(n) assuming recursion stack