The purpose is to find successor of a node on a binary tree (Inorder). One thing special about this problem is that we are given the parent node for each node.
I started by simply traversing through the tree and record all the node and store them in an arrayList. (by recursively or using a stack to traversal) This certainly works but since we are storing everything in an arrayList we have to use O(n) space which is not the optimal solution.
The correct solution is to think of all the possibilities for the successor. And actually there are only 2.
1 possibility is that this node we are given directly actually have a right child. In this case, since for this problem we are doing Inorder, that means we always travel by left — middle — right order. And that also means if that node has a right child, then it is either that right child node, or the most left child of that right child. Why? Because remember the order is left — middle- right? If that right child has any left child or if those left children have more left children, then the right child itself will not be the immediate successor of the node. Rather, the most left child will be. Because of how inorder traversal works.
Another possibility is that this node have no right child. Since, again, the order is left middle right, that will means the next node should be one of the ancestors of this node. Moreover, this node should be the first node that is not a parent that connects this node from the left side because if that parent is on the left side of this node that means we traveled them earlier than this node. Therefore, the node we are looking for will be a parent node but on the right side (meaning when we are traveling up, node.parent.right == node should be false)If there is no such node we should return null.
Below is the code for this optimal solution.
