Tuesday, May 21, 2013

Populate Inorder Successor for all nodes.

Problem: Given a Binary Tree where each node has following structure, write a function to populate next pointer for all nodes. The next pointer for every node should be set to point to in-order successor.


struct Node
{
  int data;
  struct node* left;
  struct node* right;
  struct node* next;
};



Solution: 
1. In constructor, made all node's next pointer NULL.
2. Traverse the given tree in reverse inorder traversal and keep track of previously visited node. 
3. When a node is being visited, assign previously visited node as next.

Implementation:
//Public Interface
void BTree::populateInOrderSuccessor()
{
    populateInOrderSuccessor(root); 
}

//Actual Working
void BTree::populateInOrderSuccessor(Node* node)
{
    
    Node *tempNext = NULL;
    if (node)
    {
        populateInOrderSuccessor(node->right);
        node->next = tempNext;
        tempNext = node;
        populateInOrderSuccessor(node->left);
    }
}

No comments:

Post a Comment