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 inorder successor.
struct Node
{
int data;
struct node* left;
struct node* right;
struct node* next;
};
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