Wednesday, February 8, 2012

[Amazon Online Test] : Finding the inorder successor

Given a binary search tree with the following node structure

struct tree {
    int data;
    struct tree *left;
    struct tree *right;
    struct tree *next;
};
The next pointer of each node is pointing to null.
Write a code to initialize the next pointer of each node to its inorder successor.

Approach:

Traverse in the BST in reverse inorder manner(i.e. postorder) and initialize the inorder successor as the last element visted.

Below piece of code initializes the next element to the inorder successor.

void inorder_successor(struct node * root) {
     static struct node * current = NULL;
     if(root == NULL)
         return;
     inorder(root->right);
     root->next = current;
     current = root;
     inorder(root->left);
     return;
}

2 comments :

  1. We can use reverse inorder traversal and a static node to store the inorder successor in recursive manner.We can also store a reference to the inorder successor and pass it as argument.

    void setInorderSucc(Node *root)
    {
    if(!root) return;
    if(isleaf(root)) return;
    helper(root);
    }
    void helper(Node *p)
    {
    static Node *Insucc=NULL;
    if(!p) return;

    if(p->right) helper(p->right);
    p->next=Insucc;
    Insucc=p;
    if(p->left) helper(p->left);
    }

    ReplyDelete
  2. Using Modified inorder traverse we can perform this task.
    1>First visit righ->child
    2>root
    3>the visit left->child
    In b/w them we could keep track of last visited node which is nothing but the inorder successor of current node.

    for greastest element we need to take that there is no inorder successor of so we need to fill it as NULL

    ReplyDelete