PreOrder Successor of a Node in BST

Question

I'm trying this question for sometime but couldn't figure out the algorithm. My preference is to do it iteratively. Till now, I've figure out something but not sure on some point.

Currently, My algorithm looks like:

• First traverse the tree to find the node
• While traversing the tree, keep track of the previous node.
• if you find the node, check if left child is present then that is successor return.
• if left child is not present then check if right child is present the that is successor and return.
• if the node(is left to the parent) and don't have left or right child then we've saved the prev node earlier then either prev or prev's right child is the successor.
• But what if the node we found is in the right to parent and don't have left or right child how to find successor of this node?

May be there are many flaws in this algorithm as still I've not understand all the cases properly. If anyone has any idea or algorithm please share.

Thanks in advance.

Answer 1

when you find a node in preorder, to find its successor is just travesing to its next node.

what I was thinking first is the relationship of a node and its successor's values in pre-oder, but I found that it seems not very clear like the relationship in in-order. I think there is only one step beteen a node and its successor(if exists) : just move on travesing. So I design this algorithm.

my algorithm below is based on preorder travesal, it can run on a binary tree,not only BST.

#define NOT_FOUND -1
#define NEXT 0
#define FOUND 1

struct node {
    struct node *p;//parent,but useless here
    struct node *l;//left child
    struct node *r;//right child
    int value;
};

int travese(struct node* bnode, int* flag,int value)
{
    if(bnode == NULL)
        return 0;
    else
    {
        if(*flag == FOUND)
            //when the successor is found,do pruning.
            return 1;
        else if(*flag == NEXT) {
            printf("successor:%d\n",bnode->value);
            *flag = FOUND;
            return 1;
        }
        else if(*flag == NOT_FOUND && bnode->value == value)
            *flag = NEXT;
        travese(bnode->l,flag,value);
        travese(bnode->r,flag,value);
    }
    return 0;
}

and use it by:

int flag = NOT_FOUND;
travese(root,&flag,value);
if(flag == NEXT || flag == NOT_FOUND)
    printf("no successor.\n");

EDIT:

turning a recurrence algorithm to a iterative one is not difficult by using a stack like below:

int preorder_travese_with_stack(struct node* bnode, int* flag,int value)
{
    if(bnode == NULL)
        return 0;
    struct stack s;//some kind of implement
    push(s,bnode);
    while(NotEmpty(s) && *flag) {
        struct node *curNode = pop(s);
        if(*flag == NEXT) {
            printf("successor:%d\n",curNode->value);
            *flag = FOUND;
            return 1;
        }
        else if(*flag == NOT_FOUND && curNode->value == value)
            *flag = NEXT;
        push(s,curNode->r);
        push(s,curNode->l);
    }
    return 0;
}

but according to your comment and original description, I think the one you want is iterative algorithm without a stack.here it is.

After thinking ,searching and trying, I wrote one. When travse the tree iteratively without stack , the parent of a node is not useless any more. In a path, some nodes is visited not only once, and you need to record its direction at that time.

int preorder_travese_without_stack(struct node *root,int value,int *flag)
{
    int state=1;
    //state: traveral direction on a node
    //1 for going down 
    //2 for going up from its left chlid
    //3 for going up from its right child
    struct node *cur = root;
    while(1) {
        if(state == 1) //first visit
        {
            //common travese:
            //printf("%d ",cur->value);

            if(cur->value == value && *flag == NOT_FOUND)
                *flag = NEXT;
            else if (*flag==NEXT) {
                *flag = FOUND;
                printf("successor:%d\n",cur->value);
                break;
            }
        }
        if((state == 1)&&(cur->l!=NULL))
            cur = cur->l;
        else if((state==1)&&(cur->l==NULL))
        {
            state = 2;
            continue;
        }
        else if(state==2) {
            if(cur->r != NULL ) {
                cur=cur->r;
                state = 1;
            }
            else
            {
                if(cur->p!=NULL)
                {
                    if(cur==cur->p->r)
                        state = 3;
                    //else state keeps 2
                    cur=cur->p;
                }
                else //cur->p==NULL
                {
                    if(cur->p->r!=NULL) 
                    {
                        cur=cur->p->r;
                        state = 1;
                    }
                    else
                        break;
                        //end up in lchild of root
                        //because root's rchild is NULL
                 }
            }   
            continue;
        }
        else //state ==3
        {
            if(cur->p!=NULL) 
            {
                if(cur==cur->p->l)
                    state = 2;
                else
                    state = 3;
                cur=cur->p;
                continue;
             }
            else
                break;
        }   
    }
}

the usage is the same as the first recurrence one.

If you are confused yet,mostly about the direction of a node , you can draw a tree and draw the path of pre-order traverse on paper,it would help.

I'm not sure there are bugs left in the code,but it works well on the tree below:

     0
   /   \
  1     2
 / \   / \
3   4 5   6

btw,"wirte down pre-order (or else) travese algorithm of a tree both by recurrence and iteration" is a common interview problem, although solving the latter by a stack is permitted.but I think the BST requirement is unnecessary in pre-order travese.

Answer 2

My implementation of the algorithm does not use the key. Therefore it is possible to use it in any kind of binary tree, not only in Binary search trees. The algorith I used is this:

1. if given node is not present, return NULL
2. if node has left child, return left child
3. if node has right child, return right child
4. return right child of the closest ancestor whose right child is present and not yet processed

Bellow there is my solution.

TreeNode<ItemType>*  CBinaryTree<ItemType>::succesorPreOrder(TreeNode<ItemType> *wStartNode)
{

//if given node is not present, return NULL
if (wStartNode == NULL) return NULL;
/* if node has left child, return left child */
if (wStartNode->left != NULL) return wStartNode->left;
/* if node has right child, return right child */
if (wStartNode->right != NULL) return wStartNode->right;
/* if node isLeaf
return right child of the closest ancestor whose right child is present and not yet processed*/
if (isLeaf(wStartNode)) {
    TreeNode<ItemType> *cur = wStartNode;
    TreeNode<ItemType> *y = wStartNode->parent;

    while (y->right == NULL && y->parent!=NULL){
        cur = y;
        y = y->parent;
    }
    while (y != NULL && cur == y->right) {
        cur = y;
        y = y->parent;
    }
    return y->right;
}

}

bool CBinaryTree<ItemType>::isLeaf(TreeNode<ItemType> *wStartNode){
if (wStartNode->left == NULL && wStartNode->right == NULL) return true;
else return false;
};