Root of the binary tree was given with an extra pointer pointing to it's parent as shown below and TreeNode is given as an input. Program should return it's next inorder successor.

class TreeNode {
 public int val;
 public TreeNode left;
 public TreeNode right;
 public TreeNode parent;
}

					   1
				    /      \
		         6           8
		       /   \       /   \  
		     2      3    10     4


It's inorder traversal is [2,6,3,1,10,8,4]

input and output.
[2,6,3,1,10,8,4], 8 => 4
[5, 8, 9, 10], 9 => 10
[1,2,3,4,5], 5 => null.

Solution:
There are few cases that we need to cover to solve this problem.
Basic inorder traversal is to visit (left, root, right).

1. If the given node (n) has a right node then it is easy, traverse to the left most node in the right subtree. ( we got the answer).
2. If it doesn't have the right node this is where it gets tricky. we have to go up the tree using the parent node
   1. if its parent nodes left node is equal to n, then found the answer.
   2. If parents left node is not equals to n, keep traversing it's parent node by keeping track of it's previous parents.

public TreeNode InOrderSuccessor(TreeNode node) {
	if(node == null) return null;
	// traverse left most node in the right subtree.
	if(node.right != null) {
		while(node.left != null) {
			node = node.left;
		}
		return node;
	} else {
		TreeNode previous = node;
		TreeNode current = node.parent;
		 while(current != null && current.left != previous) {
			  previous = current
			  current = current.parent;
		 }
		 return current;
	}
}

Solution Ref: CTCI