Posted tagged ‘inorder’

Adding to each node the next inorder successor node in a binary tree

February 3, 2012

Lately I came to a question which stated that Given a Binary tree where each node has an extra field (node * next), write a function that puts the inorder successor of that node in the next pointer.

This can be petty easily done using the general Inorder traversal algorithm of binary trees, but in the code shown below, as you can see, I am using a global variable (which I don’t think is a good practice). If anyone turns up with a method that doesn’t use a global variable, please share the link.

I have added the necessary comments to my code so that even novices don’t have a problem in understanding it.

(Since wordpress has a bad habit of removing the spaces I put in my code x-( , you can have a better view at this gist )

// Global var to contain the inorder predecessor
node * prev;

void add_inorder(node * nd)
{
// Base case
if (nd == NULL)
return;

// Recursive call for inorder processing
add_inorder(nd->left);

// The current node has a predecessor
if (prev != NULL)
{
// Set the next pointer
prev->next = nd;
prev = nd;
}

// This is the first node in the inorder processing
else
{
prev = nd;
}

// Recursive call for inorder processing
add_inorder(nd->right);
}

void mark_inorder(node * root)
{
/* assuming the structure to be:
typedef struct node{
int val;
struct node * next;
struct node * left;
struct node * right;
} */

// Initialising the global variable
prev = NULL;
// calling the function to add the values to pointers
add_inorder(root);
// Complete the next pointers by adding to the next
// pointer of last node in inorder processing, NULL
prev->next = NULL;
}
Advertisements

%d bloggers like this: