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;

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.

//Public Interface
void BTree::populateInOrderSuccessor()

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

No comments:

Post a Comment