Find Successor

Naive solution

The first solution or the simplest solution that comes to mind when solving inorder successor problem is:

1. Compute the inorder traversal of the binary tree.
2. Store the results in an array.
3. Traverse the array to find the target node.
4. Return the next element in the array if it exists, otherwise return null.

According the the example:

The inorder traversal is computed as:

• Traverse left subtree.
• Print / store the value of the current node.
• Traverse right subtree.

inorderArr = [6, 4, 2, 5, 1, 3]

Now, The successor of node 5 will be 1 Because 1 occurs right next to 5.

Time Complexity

• O(n) Because we have to inorder traverse the tree and then iterate over the array to find the desired value.

Optimal Approach

To get the inorder successor of a Binary Tree, we need to take care of 3 steps:

• Right child of node is not NULL. If the right child of the node is not NULL then the inorder successor of this node will be the leftmost node in it's right subtree.
• Right Child of the node is NULL. If the right child of node is NULL. Then we keep finding the parent of the given target node, such that targetNode.left = x. For example in the above given tree, inorder successor of node 5 will be 1. First parent of 5 is 2 but 2->left != 5. So next parent of 2 is 1, now 1->left = 2. Therefore, inorder successor of 5 is 1.
• If node is the rightmost node. If the node is the rightmost node in the given tree. For example, in the above tree node 3 is the right most node. In this case, there will be no inorder successor of this node. i.e. Inorder Successor of the rightmost node in a tree is NULL.

Time Complexity:

• O(h) in average case if the tree is not skewed.