Algo#3: Postorder Predecessor in Binary Tree

Postorder Predecessor value for any node X means value of node Y that comes just before node X while doing Postorder traversal. For given tree in figure, postorder traversal (Left Right Root) would be : 4 5 2 6 3 1. We can search postorder predecessor for any node by just looking at this traversal output. E.G. postorder predecessor of node '5' is node '4' because '4' appears before '5' in given traversal.

But in real life we encounter Postorder Predecessor to be search for randomly any node, and if we go by this method of doing postorder traversal first then giving predecessor, it would be inefficient because of its time complexity of O(n) in large trees. So we need some method which can return Postorder Predecessor randomly for any node without doing traversal explicitly in less time complexity.

Luckily postorder traversal follows some pattern which can help us in giving Postorder Predecessor for any node without doing traversal at all.

Following is simple algorithm for finding Postorder Predecessor of binary tree.

Step 1: If current root is NULL, then pred(current root) is NULL.

Step 2: If current root is target node for which we are looking for predecessor.

        2.1: If current root has a right child, r, then pred(current root) is r.

        2.2: Otherwise If current root has a left child, l, then pred(current root) is l.

        2.3: Otherwise if current root has a left sibling, ls, then pred(current root) is ls

      2.4: Otherwise if current root has an ancestor, v, which is a right child and has a left sibling, vls, then pred(current root) is vls

        2.5: Otherwise, pred(current root) is undefined.

Step 3: Current root is not the target node for which we are looking predecessor.

        3.1: Search target node and its predecessor in left side of tree recursively, and return if found.

        3.2: Search target node and its predecessor in right side of tree recursively, and return.

Following is implementation of above algorithm in c language.

Please write comments if you find anything wrong or you want to add something more related to this topic.