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.

Initially, all next pointers have NULL values. Your function should fill these next pointers so that they point to inorder successor.

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);

}

`struct` `node` `{` ` ` `int` `data;` ` ` `struct` `node* left;` ` ` `struct` `node* right;` ` ` `struct` `node* next;` `}` |

**Method 1:Reverse Inorder Traversal**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);

}

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

ReplyDeleteMob: +91-9891445495, +91-8448366515, +918587026175

Phone : +91-11-23657121

Website : http://civillabequipmentmanufacturer.com, http://setestindia.com