Algo#5: Preorder Predecessor in Binary Tree

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

But in real life we encounter Preorder Predecessor to be search for randomly any node, and if we go by this method of doing preorder 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 Preorder Predecessor randomly for any node without doing traversal explicitly in less time complexity.

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

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

Step 1: Current root itself is NULL, then predecessor is also NULL.

Step 2: Current root contains value same as key for which we are looking predecessor.

        2.1: If current root is the root of the tree, then pred(current root) is undefined

        2.2: If u has a left sibling, ls, then pred(current root) is the rightmost descendant of ls
        2.3: Otherwise, pred(current root) is parent(current root).

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.