Posted tagged ‘binary tree’

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

K distance nodes in a Binary tree

February 3, 2012

For a Given node of a binary tree, print the K distance nodes.

For the solution, you can also refer to stackoverflow. This also tells that only one ancestor can be at K distance from a given node.

Source code: (written in C)

void K_dist_children(node * nd, int K)
{
// Base case
// The Kth child found
if(K==0)
{
printf("%d\n", nd->val);
return;
}

// K distance node from nd are at
// K-1 distance from children of current node
K_dist_children(nd->left, K-1);
K_dist_children(nd->right, K-1);
}

int K_dist_ancestor(node * cur,    //curent node
node * search, //node being searched
int K)
{
// If the node is found, return back the result
if (cur == search)
{
return K-1;
}

int n1, n2;

// recursively search for the node in the tree
n1 = K_dist_ancestor(cur->left, search, K);
n2 = K_dist_ancestor(cur->right, search, K);

// PS: n1 & n2 can't be non-(-1) at the same time

// if node found in any of the sub trees
if((n1 == -1) && (n2 == -1))
return -1;

// node found in right subtree
if((n1 == -1))
{
// the current node is at distance K
if(n2 == 0)
printf("%d", cur->val);

// return back the distance
return (n2-1);
}

// node found in left subtree
if((n2 == -1))
{
// the current node is at distance K
if(n1 == 0)
printf("%d", cur->val);

// return back the distance
return (n1-1);
}
}

void print_K_distance_nodes(node * root, node * search, int K)
{
// The structure of node is:
// struct node{
// int val;
// node * left;
// node * right;
// }

// Print the ancestor at distance K
K_dist_ancestor(root, search, K);

// Print the children at distance K
K_dist_children(search, K);
}

%d bloggers like this: