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


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
Explore posts in the same categories: C

Tags: , , ,

You can comment below, or link to this permanent URL from your own site.

2 Comments on “Adding to each node the next inorder successor node in a binary tree”

  1. Yuandong Says:

    You can change the function a little bit:
    void add_inorder(node * nd, node *&prev)


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: