Binary Search TreesProblem 6 of 22
Populate Inorder successor of all nodes
Problem Statement
Given a BST where each node has an additional pointer next, populate each node's next pointer to point to its inorder successor.
Example:
Input:
10
/ \
8 12
Output:
Node 8's next -> Node 10
Node 10's next -> Node 12
Node 12's next -> NULL
Inorder: 8 -> 10 -> 12
Approach 1: Brute Force (Store Inorder + Second Pass)
Intuition
Perform inorder traversal to get nodes in sorted order, then iterate through the list and link each node to the next.
Algorithm
- Perform inorder traversal and store nodes in a list
- Iterate through the list
- For each node, set its next pointer to the next node in the list
java
import java.util.*;
class TreeNode {
int val;
TreeNode left, right;
TreeNode next; // Inorder successor pointer
TreeNode(int x) { val = x; }
}
public class Solution {
private void inorder(TreeNode root, List<TreeNode> nodes) {
if (root == null) return;
inorder(root.left, nodes);
nodes.add(root);
inorder(root.right, nodes);
}
public void populateNextBruteForce(TreeNode root) {
List<TreeNode> nodes = new ArrayList<>();
inorder(root, nodes);
for (int i = 0; i < nodes.size() - 1; i++) {
nodes.get(i).next = nodes.get(i + 1);
}
if (!nodes.isEmpty()) {
nodes.get(nodes.size() - 1).next = null;
}
}
}Complexity Analysis
- Time Complexity: O(n) - Two passes through nodes
- Space Complexity: O(n) - Storing all nodes in list
Approach 2: Optimal (Reverse Inorder Traversal)
Intuition
Instead of storing all nodes, we can populate the next pointers during traversal itself. Using reverse inorder traversal (right, root, left), we process nodes in decreasing order. We maintain a pointer to the previously processed node, which becomes the successor of the current node.
Algorithm
- Perform reverse inorder traversal (right -> root -> left)
- Maintain a pointer to the previously visited node
- Set current node's next to the previous node
- Update previous to current node
java
class TreeNode {
int val;
TreeNode left, right;
TreeNode next;
TreeNode(int x) { val = x; }
}
public class Solution {
private TreeNode prev = null;
public void populateNext(TreeNode root) {
prev = null;
reverseInorder(root);
}
private void reverseInorder(TreeNode root) {
if (root == null) return;
// Process right subtree first
reverseInorder(root.right);
// Set next pointer to previously visited node
root.next = prev;
prev = root;
// Process left subtree
reverseInorder(root.left);
}
}Complexity Analysis
- Time Complexity: O(n) - Visit each node once
- Space Complexity: O(h) - Recursion stack only, no extra storage
Approach 3: Optimal Iterative (Morris-like Traversal)
Intuition
We can achieve O(1) space using an iterative approach with Morris traversal concept.
Algorithm
- Use standard inorder iterative approach
- Keep track of previous node
- Link previous node's next to current node
java
import java.util.*;
class TreeNode {
int val;
TreeNode left, right;
TreeNode next;
TreeNode(int x) { val = x; }
}
public class Solution {
public void populateNextIterative(TreeNode root) {
if (root == null) return;
Stack<TreeNode> stack = new Stack<>();
TreeNode curr = root;
TreeNode prev = null;
while (curr != null || !stack.isEmpty()) {
// Go to leftmost
while (curr != null) {
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
// Link previous node to current
if (prev != null) {
prev.next = curr;
}
prev = curr;
curr = curr.right;
}
// Last node's next is null
if (prev != null) {
prev.next = null;
}
}
}Complexity Analysis
- Time Complexity: O(n) - Visit each node once
- Space Complexity: O(h) - Stack space for traversal
Key Takeaways
- Reverse inorder trick: Processing right-to-left gives us successors naturally
- Maintain previous pointer: Link nodes during traversal
- Two approaches: Forward inorder (link prev to curr) vs Reverse inorder (link curr to prev)
- Space optimization: Reverse inorder with recursion uses only O(h) space
- Similar concept used in "Flatten BST to Linked List"
- Understanding this helps with threaded binary trees
- The next pointer essentially creates a linked list overlay on the BST