Saturday, February 4, 2012

Populate Inorder successor in BST

Given a Binary Search 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 inorder successor.
struct node
{
  int data;
  struct node* left;
  struct node* right;
  struct node* next;
}
Initially, all next pointers have NULL values. Your function should fill these next pointers so that they point to inorder successor.

Method 1:Reverse Inorder Traversal
Traverse the given tree in reverse inorder traversal and keep track of previously visited node. When a node is being visited, assign previously visited node as next.

void populateNextRecur(struct tree* node, struct tree *&next_ref)
{
    if (node)
    {
        populateNextRecur(node->right, next_ref);

        node->next = next_ref;

        next_ref = node;

        populateNextRecur(node->left, next_ref);
    }
}

void populateNext(struct tree *root)
{
    struct tree *next = NULL;
    populateNextRecur(root, next);
}

1 comment:

  1. Civil Lab Equipment Manufacturer offer a comprehensive range of oil and petroleum testing lab equipments, which are widely used in Schools, Colleges and Universities.

    Mob: +91-9891445495, +91-8448366515, +918587026175
    Phone : +91-11-23657121
    Website : http://civillabequipmentmanufacturer.com, http://setestindia.com

    ReplyDelete