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