WAP to Find Level Order Successor of Node in Binary Tree

1) Using the parent pointer, get the level of the given node. Also, get the root of the tree.

int level = 1;
struct node *temp = node;

/* Find the level of the given node and root of the tree */
while(temp->parent != NULL)
{
temp = temp->parent;
level++;
}
/* temp is now root of the tree and level is level of the node */

2) Once we have level of the given node and root of the tree, traverse the tree from root to the calculated level + 1. We are traversing one extra level for the case when given node is the rightmost node of its level. While traversing if you visit the given node, mark visited flag as 1. Print the node just after the visited flag.


#include
#include

/* Note the structure of root. It has data and pointers to left childe, right child and
parent node */
struct node
{
int data;
struct node *left;
struct node *right;
struct node *parent;
};

/* Prints the level order successor of node
root --> root of the tree
level --> level of node */
void _print(struct node* root, struct node *node, int level)
{
static int visited = 0;
if(root == NULL)
return;
if(level == 1 || level == 1)
{
/* If the given node is visited then print the current root */
if(visited == 1)
{
printf("Level Order Successor is %d ", root->data);
visited = 0;
return;
}
/* If the current root is same as given node then change the visited flag
so that current node is printed */
if(root == node)
visited = 1;
}
else if (level > 1)
{
_print(root->left, node, level-1);
_print(root->right, node, level-1);
}
}

void printLevelOrderSuccessor(struct node *node)
{
int level = 1;
struct node *temp = node;

/* Find the level of the given node and root of the tree */
while(temp->parent != NULL)
{
temp = temp->parent;
level++;
}
_print(temp, node, level);
}

/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
node->parent = NULL;
return(node);
}

/* Driver program to test above functions*/
int main()
{
struct node *root = newNode(1);
root->parent = NULL;
root->left = newNode(2);
root->right = newNode(3);
root->left->parent = root;
root->right->parent = root;

root->left->left = newNode(4);
root->right->right = newNode(5);

root->left->left->parent = root->left;
root->right->right->parent = root->right;

// printf("\n Level order successor of %d is: ", root->right->data);
printLevelOrderSuccessor(root->left->left);

getchar();
return 0;
}

Source Geeks4Geeks