Populate Inorder Successor for all nodes

Last Updated : 21 Dec, 2022

Given a Binary Tree where each node has the following structure, write a function to populate the next pointer for all nodes. The next pointer for every node should be set to point to in-order successor.

C++

class node {
public:
    int data;
    node* left;
    node* right;
    node* next;
};
 
// This code is contributed
// by Shubham Singh

C

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

Java

// A binary tree node
class Node {
    int data;
    Node left, right, next;
 
    Node(int item)
    {
        data = item;
        left = right = next = null;
    }
}
 
// This code is contributed by SUBHAMSINGH10.

Python3

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
        self.next = None
 
# This code is contributed by Shubham Singh

C#

class Node {
    public int data;
    public Node left, right, next;
 
    public Node(int item)
    {
        data = item;
        left = right = next = null;
    }
}
Node root;
 
// This code is contributed
// by Shubham Singh

Javascript

<script>
class Node
{
 
    constructor(x) {
        this.data = x;
        this.left = null;
        this.right = null;
      }
}
 
// This code is contributed by Shubham Singh
</script>

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

Solution (Use Reverse Inorder Traversal)
Traverse the given tree in reverse inorder traversal and keep track of previously visited node. When a node is being visited, assign a previously visited node as next.

C++

// C++ program to populate inorder
// traversal of all nodes
#include <bits/stdc++.h>
using namespace std;
 
class node {
public:
    int data;
    node* left;
    node* right;
    node* next;
};
 
/* Set next of p and all descendants of p
by traversing them in reverse Inorder */
void populateNext(node* p)
{
    // The first visited node will be the
    // rightmost node next of the rightmost
    // node will be NULL
    static node* next = NULL;
 
    if (p) {
        // First set the next pointer
        // in right subtree
        populateNext(p->right);
 
        // Set the next as previously visited
        // node in reverse Inorder
        p->next = next;
 
        // Change the prev for subsequent node
        next = p;
 
        // Finally, set the next pointer in
        // left subtree
        populateNext(p->left);
    }
}
 
/* UTILITY FUNCTIONS */
/* Helper function that allocates a new
node with the given data and NULL left
and right pointers. */
node* newnode(int data)
{
    node* Node = new node();
    Node->data = data;
    Node->left = NULL;
    Node->right = NULL;
    Node->next = NULL;
 
    return (Node);
}
 
// Driver Code
int main()
{
 
    /* Constructed binary tree is
            10
            / \
        8 12
        /
    3
    */
    node* root = newnode(10);
    root->left = newnode(8);
    root->right = newnode(12);
    root->left->left = newnode(3);
 
    // Populates nextRight pointer in all nodes
    populateNext(root);
 
    // Let us see the populated values
    node* ptr = root->left->left;
    while (ptr) {
        // -1 is printed if there is no successor
        cout << "Next of " << ptr->data << " is "
             << (ptr->next ? ptr->next->data : -1) << endl;
        ptr = ptr->next;
    }
 
    return 0;
}
 
// This code is contributed by rathbhupendra

Java

// Java program to populate inorder traversal of all nodes
 
// A binary tree node
class Node {
    int data;
    Node left, right, next;
 
    Node(int item)
    {
        data = item;
        left = right = next = null;
    }
}
 
class BinaryTree {
    Node root;
    static Node next = null;
 
    /* Set next of p and all descendants of p by traversing
       them in reverse Inorder */
    void populateNext(Node node)
    {
        // The first visited node will be the rightmost node
        // next of the rightmost node will be NULL
        if (node != null) {
            // First set the next pointer in right subtree
            populateNext(node.right);
 
            // Set the next as previously visited node in
            // reverse Inorder
            node.next = next;
 
            // Change the prev for subsequent node
            next = node;
 
            // Finally, set the next pointer in left subtree
            populateNext(node.left);
        }
    }
 
    /* Driver program to test above functions*/
    public static void main(String args[])
    {
        /* Constructed binary tree is
            10
           /   \
          8      12
         /
        3    */
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(10);
        tree.root.left = new Node(8);
        tree.root.right = new Node(12);
        tree.root.left.left = new Node(3);
 
        // Populates nextRight pointer in all nodes
        tree.populateNext(tree.root);
 
        // Let us see the populated values
        Node ptr = tree.root.left.left;
        while (ptr != null) {
            // -1 is printed if there is no successor
            int print
                = ptr.next != null ? ptr.next.data : -1;
            System.out.println("Next of " + ptr.data
                               + " is: " + print);
            ptr = ptr.next;
        }
    }
}
 
// This code has been contributed by Mayank Jaiswal

Python3

# Python3 program to populate
# inorder traversal of all nodes
 
# Tree node
 
 
class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
        self.next = None
 
 
# The first visited node will be
# the rightmost node next of the
# rightmost node will be None
next = None
 
# Set next of p and all descendants of p
# by traversing them in reverse Inorder
 
 
def populateNext(p):
 
    global next
 
    if (p != None):
 
        # First set the next pointer
        # in right subtree
        populateNext(p.right)
 
        # Set the next as previously visited node
        # in reverse Inorder
        p.next = next
 
        # Change the prev for subsequent node
        next = p
 
        # Finally, set the next pointer
        # in left subtree
        populateNext(p.left)
 
# UTILITY FUNCTIONS
# Helper function that allocates
# a new node with the given data
# and None left and right pointers.
 
 
def newnode(data):
 
    node = Node(0)
    node.data = data
    node.left = None
    node.right = None
    node.next = None
 
    return(node)
 
# Driver Code
 
 
# Constructed binary tree is
#         10
#     / \
#     8     12
# /
# 3
root = newnode(10)
root.left = newnode(8)
root.right = newnode(12)
root.left.left = newnode(3)
 
# Populates nextRight pointer
# in all nodes
p = populateNext(root)
 
# Let us see the populated values
ptr = root.left.left
while(ptr != None):
 
    out = 0
    if(ptr.next != None):
        out = ptr.next.data
    else:
        out = -1
 
    # -1 is printed if there is no successor
    print("Next of", ptr.data, "is", out)
    ptr = ptr.next
 
# This code is contributed by Arnab Kundu

C#

// C# program to populate inorder traversal of all nodes
using System;
 
class BinaryTree {
    // A binary tree node
    class Node {
        public int data;
        public Node left, right, next;
 
        public Node(int item)
        {
            data = item;
            left = right = next = null;
        }
    }
    Node root;
    static Node next = null;
 
    /* Set next of p and all descendants of p by traversing
       them in reverse Inorder */
    void populateNext(Node node)
    {
        // The first visited node will be the rightmost node
        // next of the rightmost node will be NULL
        if (node != null) {
            // First set the next pointer in right subtree
            populateNext(node.right);
 
            // Set the next as previously visited node in
            // reverse Inorder
            node.next = next;
 
            // Change the prev for subsequent node
            next = node;
 
            // Finally, set the next pointer in left subtree
            populateNext(node.left);
        }
    }
 
    /* Driver program to test above functions*/
    static public void Main(String[] args)
    {
        /* Constructed binary tree is
            10
           /   \
          8      12
         /
        3    */
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(10);
        tree.root.left = new Node(8);
        tree.root.right = new Node(12);
        tree.root.left.left = new Node(3);
 
        // Populates nextRight pointer in all nodes
        tree.populateNext(tree.root);
 
        // Let us see the populated values
        Node ptr = tree.root.left.left;
        while (ptr != null) {
            // -1 is printed if there is no successor
            int print
                = ptr.next != null ? ptr.next.data : -1;
            Console.WriteLine("Next of " + ptr.data
                              + " is: " + print);
            ptr = ptr.next;
        }
    }
}
 
// This code has been contributed by Arnab Kundu

Javascript

<script>
// Javascript program to populate inorder traversal of all nodes
   
    // A binary tree node
    class Node
    {
     
        constructor(x) {
            this.data = x;
            this.left = null;
            this.right = null;
          }
    }
     
    let root;
    let next = null;
        
    /* Set next of p and all descendants of p by traversing them in
       reverse Inorder */
    function populateNext(node)
    {
        // The first visited node will be the rightmost node
        // next of the rightmost node will be NULL
        if (node != null)
        {
            // First set the next pointer in right subtree
            populateNext(node.right);
   
            // Set the next as previously visited node in reverse Inorder
            node.next = next;
   
            // Change the prev for subsequent node
            next = node;
   
            // Finally, set the next pointer in left subtree
            populateNext(node.left);
        }
    }
     
    /* Driver program to test above functions*/
     
    /* Constructed binary tree is
            10
           /   \
          8      12
         /
        3    */
    root = new Node(10)
    root.left = new Node(8)
    root.right = new Node(12)
    root.left.left = new Node(3)
  
    // Populates nextRight pointer
    // in all nodes
    p = populateNext(root)
  
    // Let us see the populated values
    ptr = root.left.left
     
    while (ptr != null)
        {
            // -1 is printed if there is no successor
            let print = ptr.next != null ? ptr.next.data : -1;
            document.write("Next of " + ptr.data + " is: " + print+"<br>");
            ptr = ptr.next;
        }
     
    // This code is contributed by unknown2108
</script>

Output

Next of 3 is 8
Next of 8 is 10
Next of 10 is 12
Next of 12 is -1

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

GeeksforGeeks

Improve

Previous Article

Find all possible binary trees with given Inorder Traversal

Construct Complete Binary Tree from its Linked List Representation

Similar Reads

Inorder predecessor and successor for a given key in BST | Iterative Approach

Given a BST and a key. The task is to find the inorder successor and predecessor of the given key. In case, if either of predecessor or successor is not present, then print -1.Examples: Input: 50 / \ / \ 30 70 / \ / \ / \ / \ 20 40 60 80 key = 65 Output: Predecessor : 60 Successor : 70 Input: 50 / \ / \ 30 70 / \ / \ / \ / \ 20 40 60 80 key = 100 O

Inorder Successor in Binary Search Tree

In Binary Tree, Inorder successor of a node is the next node in Inorder traversal of the Binary Tree. Inorder Successor is NULL for the last node in Inorder traversal. In Binary Search Tree, Inorder Successor of an input node can also be defined as the node with the smallest key greater than the key of the input node. So, it is sometimes important

Inorder predecessor and successor for a given key in BST

There is BST given with root node with key part as integer only. The structure of each node is as follows: C/C++ Code struct Node { int key; struct Node *left, *right ; }; Java Code static class Node { int key; Node left, right ; }; // This code is contributed by gauravrajput1 C/C++ Code class Node: def __init__(self, key): self.key = key self.left

Replace each node in binary tree with the sum of its inorder predecessor and successor

Given a binary tree containing n nodes. The problem is to replace each node in the binary tree with the sum of its inorder predecessor and inorder successor. Examples: Input : 1 / \ 2 3 / \ / \ 4 5 6 7 Output : 11 / \ 9 13 / \ / \ 2 3 4 3 For 1: Inorder predecessor = 5 Inorder successor = 6 Sum = 11 For 4: Inorder predecessor = 0 (as inorder predec

Inorder Successor of a node in Binary Tree

Given a binary tree and a node, we need to write a program to find inorder successor of this node.Inorder Successor of a node in binary tree is the next node in Inorder traversal of the Binary Tree. Inorder Successor is NULL for the last node in Inorder traversal. In the above diagram, inorder successor of node 4 is 2 and node 5 is 1. We have alrea

Pre-Order Successor of all nodes in Binary Search Tree

Consider a BST(Binary Search Tree) where duplicates are not allowed.Given a key present in the BST. The task is to find its pre-order successor in this BST i.e. the task is to find a key that comes next to the given key if we apply a pre-order traversal on given BST. Example: Insert the following keys in a BST in the same order: 51, 39, 31, 54, 92,

Common nodes in the inorder sequence of a tree between given two nodes in O(1) space

Given a binary tree consisting of distinct values and two numbers K1 and K2, the task is to find all nodes that lie between them in the inorder sequence of the tree. Examples: Input: 1 / \ 12 11 / / \ 3 4 13 \ / 15 9 k1 = 12 k2 = 15 Output: 1 4 Explanation: Inorder sequence is 3 12 1 4 15 11 9 13 The common nodes between 12 and 15 in the inorder se

Find a set of at most N/2 nodes from a Graph such that all remaining nodes are directly connected to one of the chosen nodes

Given an integer N, representing the number of nodes present in an undirected graph, with each node valued from 1 to N, and a 2D array Edges[][], representing the pair of vertices connected by an edge, the task is to find a set of at most N/2 nodes such that nodes that are not present in the set, are connected adjacent to any one of the nodes prese

Sum of the mirror image nodes of a complete binary tree in an inorder way

Given a complete binary tree, the task is to find the sum of mirror image nodes in an inorder way i.e. find the inorder traversal of the left sub-tree and for every node traversed, add the value of its mirror node to the current node's value. Examples: Input: Output: 20 51 19 10 Inorder traversal of the left sub-tree of the given tree is 4 23 11 5.

Postorder successor of a Node in Binary Tree

Given a binary tree and a node in the binary tree, find Postorder successor of the given node. Examples: Consider the following binary tree 20 / \ 10 26 / \ / \ 4 18 24 27 / \ 14 19 / \ 13 15 Postorder traversal of given tree is 4, 13, 15, 14, 19, 18, 10, 24, 27, 26, 20. Input : Complexity Analysis:24 Output : 27 Input : 4 Output : 13 A simple solu

Article Tags :

DSA
Tree

Practice Tags :

Tree