Data Structuresand Algorithms Good OldJava AdvancedInterview Topics Cloud andDatabases Web Designand Development Must-knowTools Good ToKnow

## Find inorder successor in a tree if each node has parent pointer

We need to consider the following different cases:

1) If a node has right child, then left-most child of this right subtree is the successor.

2) If no right child is there, then 2 cases occur:

a) If current node is left child of its parent, then parent is the successor.

b) If current node is right child of its parent, then continue traversing the parent till a parent is found in whose left child current tree lies.

With these considerations, the code can be written as:

```TreeNode inorderSuccessor(TreeNode n)
{
if (n == null) return null;

if (n.right != null)
return leftMostChild(n.right);

// Go up until we are left grandchildren of some node
TreeNode p;
while (n.parent != null)
{
p = n.parent;
if (p.left == n)
return p;
n = p;
}
return null;
}
```

Like us on Facebook to remain in touch
with the latest in technology and tutorials!

Got a thought to share or found a
bug in the code?
We'd love to hear from you:

 Name: Email: (Your email is not shared with anybody) Comment: