In-order successor of given node in the BST

Given a binary search tree and a node in it, find the in-order successor of that node in the BST.

There are just two cases:

1. The easier one: p has right subtree, then its successor is just the leftmost child of its right subtree;
2. The harder one: p has no right subtree, then a traversal is needed to find its successor.

TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
 4         if (p.right!=NULL) 

               return leftMost(p -> right);
 5         TreeNode succ = NULL;
 6         while (root!=null) {
 7             if (p.val < root.val) {
 8                 succ = root;
 9                 root = root.left;
10             }
11             else if (p.val > root.val)
12                 root = root.right; 
13             else 

                   break;
14         }
15         return suc;
16     }

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)