Populate Inorder Successor for all nodes

JavaView on GFG

Time: O(n)

Space: O(h)

Intuition

Set "next" pointer of each BST node to its in-order successor.

Algorithm

1Reverse in-order (right-root-left). Maintain prev pointer. Set curr.next = prev. Update prev = curr.

Common Pitfalls

•Reverse in-order sets successors correctly. Or: standard in-order, track previous node and set its next to current.

Populate Inorder Successor for all nodes.java

Java

// Approach: Reverse in-order traversal (right-root-left). Track the previous node and assign as successor.
// Time: O(n) Space: O(h)
class Node {
    int data;
    Node left, right, next;

    public Node(int data) {
        this.data = data;
    }
}

class Solution {
    Node prev = null;

    public void populateNext(Node root) {
        Node prev = null;
        IOT(root);
        if (prev != null)
            prev.next = null;
    }

    private void IOT(Node root) {
        if (root == null)
            return;

        IOT(root.left);

        if (prev != null)
            prev.next = root;

        prev = root;
        IOT(root.right);
    }
}

Was this solution helpful?