**Question: Write a non-recursive algorithm to find the pre-order successor of a given node in a BST.**

**Solution:**

Let me tell you the background first. There are basically three kind of traversal for a binary tree. Each traversal is named on the basis of processing of root node. For example in preorder traversal, root will be processed before any other node, in postorder, root will be processed only after all the nodes are processed.

**Following is the order of processing in each traversal:**

**Pre-Order: ** root–>left–>right

**Post-Order: ** left–>right–>root

**In-Order: ** left–>root–>right

When I say left/right, it means left/right sub tree and not just the child node.

Now back to our main problem. If you look at pre-order traversal given above, we can easily find out the pre-order successor of an internal node. But, problem comes when it is a leaf node. Look at the pre-order traversal again, according to it, once you reach at any leaf node, you have to go to right sub tree of an ancestor which is not yet processed. So, root of that right sub tree will be the pre-order successor of that leaf node which you are considering at any point of time.

Please find the algorithm herein below:

- if given node is not present, return null
- if node has left child, return left child
- if node has right child, return right child
- return right child of the closest ancestor whose right child is present and not yet processed

I have implemented the code for the same algorithm, find it below:

public static BST getPreorderSuccessor(BST root, int val){

if( root == null || (root.getLeft() == null && root.getRight() == null))

return null;

BST temp = root;

BST ancestor = null;

while(temp != null && temp.getVal() != val){

if(val < temp.getVal()){

if(temp.getRight() != null){

ancestor = temp;

}

temp = temp.getLeft();

}else{

temp = temp.getRight();

}

}

// node not found case

if(temp == null)

return null;

if(temp.getLeft() != null)

return temp.getLeft();

if(temp.getRight() != null)

return temp.getRight();

if(ancestor != null)

return return ancestor.getRight();

return null;

}