Navigation Menu

Skip to content

Instantly share code, notes, and snippets.

@ayushgoel
Created February 3, 2012 11:02
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save ayushgoel/1729674 to your computer and use it in GitHub Desktop.
Save ayushgoel/1729674 to your computer and use it in GitHub Desktop.
Linking inorder successor in a binary tree
// 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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment