CODEWITHSUNDEEP
algorithmdata-structuresrecursiontree
siva
siva

Reputation: 1731

Question on Tree Data Structure: How can we fill all inorder successor pointer of all tree nodes?

Tree node contains 3 pointers *left, *right and *Successor .

Struct node{
     int data;
     struct node *left;
     struct node *right;
     struct node *successor; 
}; 


        A
       /  \
      B    C
     / \  / \
    D   E F  G

INORDER Traversal: DBEAFCG *Note:* A inorder successors are F,C and G.

  **Function prototype:** void  FillSuccessorNodes( struct node *root);

Tree's root node given to us and we need to fill successor pointer for all nodes.

case 1) some of the Successor pointers may be NULL . This case you have to fill that pointer with immediate Inorder Successor.

Example: if A->Successor == NULL, then fill A->Successor = F

case 2) some of the Successor pointers may already points to correct successors. This case You no need to modify successor pointers.

Example: 1) A->successor = F is valid

     2) A->successor = C is valid

     3) A-successor = G is valid  . All these three cases you no need to modify successor pointer since these already pointing to correct successor nodes.

case 3) Some of the successor pointers are not NULL but these pointers pointing to INVALID successors i.e it could be inorder successor or some garbage value. This case you have to fill these nodes with immediate successor nodes.

Example:

     1) A->successor = B is invalid since B is not successor node , so we have to correct it to A->successor = F.

     2) A->successor = 0x23237463478 is invalid since it is pointing to garbage value. So we we have to correct it to A->successor = F.

1) Interviewer asked me time efficient solution in O(n) time complexity. Extra space allowed. 2) she gave some hint i.e we can use HASHing.

If you know the solution for this problem, please let me know .

Upvotes: 0

Views: 1072

Answers (2)

ttk
ttk

Reputation: 160

It require only a small modification to inorder traversal , you have to remeber the predecessor and set predecessot->successor = current.

stack<node*> s;
node* t = root ,*pred=NULL;
while(true)
{
    if(t){
            s.push(t);
            t= t->left; 
            continue;
    }           
    if(s.empty()) { break;}
    t= s.top();
    if(NULL != pred && pred->succesor != t)
    {
        pred->succesor = t;     
    }
    pred  = t; 
    s.pop();        
    cout<<t->c;
    t= t->right; 
}

Upvotes: 1

antonakos
antonakos

Reputation: 8361

The question and hint seem misleading to me. Since you have to check all nodes anyway to check if their successors are invalid, and since you have to compute the successor to know what invalid means, you might as well use a standard O(n) inorder traversal, e.g.:

#include <utility>
using namespace std;

typedef pair<node*, node*> node_pair;

node_pair setInOrderSuccessors(node* root)
{
    node_pair result(root, root);

    if (root->left) {
        const node_pair pair = setInOrderSuccessors(root->left);
        result.first = pair.first;
        pair.second->successor = root;
    }

    if (root->right) {
        const node_pair pair = setInOrderSuccessors(root->right);
        result.second = pair.second;
        root->successor = pair.first;
    }

    return result;
}

void  FillSuccessorNodes(node *root)
{
    const node_pair pair = setInOrderSuccessors(root);
    pair.second->successor = 0;
}

Upvotes: 1

Related Questions