Populate Inorder Successor for all nodes

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

Sol:

Public void populateInorderSuccessor(TreeNode T)

{

   TreeNode next = NULL;

   populateInorderSuccessorRecur(T, next);

}

Private void populateInoderSuccessorRecur(TreeNode T, TreeNode next)

{

   if(T != NULL ) {

         populateInoderSuccessorRecur(T.right, next);

          // Set the next as previously visited node in reverse Inorder

         T.next = next;

         // Change the prev for subsequent node

         next = T;

         populateInoderSuccessorRecur(T.left, next);

   }

}

Time Complexity: O(n)