Skip to main content

Detect next node at same level of a key in binary tree in c

Next node of same level of tree

C program for Detect next node at same level of a key in binary tree. Here mentioned other language solution.

// Include header file
#include <stdio.h>
#include <stdlib.h>
/* 
  C program for
  Find the next node of the key at the same 
  level in the binary tree
*/
// Binary Tree node
typedef struct TreeNode
{
	// Define useful field of TreeNode
	int data;
	struct TreeNode * left;
	struct TreeNode * right;
}TreeNode;

TreeNode * getTreeNode(int data)
{
	// Create dynamic memory of TreeNode
	TreeNode * ref = (TreeNode * ) malloc(sizeof(TreeNode));
	if (ref == NULL)
	{
		// Failed to create memory 
		return NULL;
	}
	// Set node value
	ref->data = data;
	ref->left = NULL;
	ref->right = NULL;
	return ref;
}
typedef struct BinaryTree
{
	// Define useful field of BinaryTree
	struct TreeNode * root;
	int status;
	struct TreeNode * result;
}BinaryTree;

BinaryTree * getBinaryTree()
{
	// Create dynamic memory of BinaryTree
	BinaryTree * ref = 
      (BinaryTree * ) malloc(sizeof(BinaryTree));
	if (ref == NULL)
	{
		// Failed to create memory 
		return NULL;
	}
	// Set initial values
	ref->root = NULL;
	ref->status = -1;
	ref->result = NULL;
	return ref;
}
// Method which are find next node of same level
void findNextNode(BinaryTree * ref, 
                  TreeNode * temp, 
                  int level, 
                  int node)
{
	if (temp != NULL)
	{
		if (ref->status == -1 && temp->data == node)
		{
			// When found node value
			ref->status = level;
		}
		else if (ref->status == level && ref->result == NULL)
		{
			// Next node of same level
			ref->result = temp;
		}
		// Visit to left subtree
		findNextNode(ref,temp->left, level + 1, node);
		// Visit to right subtree
		findNextNode(ref,temp->right, level + 1, node);
	}
}
// This are handling the request of to finding next
// node in same level by given node
void nextNode(BinaryTree * ref, int node)
{
	// Reset the result indicator
	ref->status = -1;
	ref->result = NULL;
	// Find next node
	findNextNode(ref, ref->root, 0, node);
	printf("\n Node : %d\n", node);
	printf(" Result : ");
	// Test Case
	if (ref->status == -1)
	{
		// Case A
		// When node values are not exist
		printf("Not found\n");
	}
	else if (ref->result == NULL)
	{
		// Case B
		// When next node is not found
		printf("None\n");
	}
	else
	{
		// Case C
		// When next node are exist
		printf("%d\n",ref->result->data);
	}
}
int main()
{
	// Create new tree
	BinaryTree * tree = getBinaryTree();
	/*
	   Make A Binary Tree
	  ---------------------
	        1
	       / \ 
	      /   \ 
	     /     \
	    2       4
	   /       / \
	  /       /   \
	  3      6     5
	   \      \   /
	    7      8 11
	              
	*/
	// Add node in Binary Tree
	tree->root = getTreeNode(1);
	tree->root->left = getTreeNode(2);
	tree->root->left->left = getTreeNode(3);
	tree->root->left->left->right = getTreeNode(7);
	tree->root->right = getTreeNode(4);
	tree->root->right->right = getTreeNode(5);
	tree->root->right->right->left = getTreeNode(11);
	tree->root->right->left = getTreeNode(6);
	tree->root->right->left->right = getTreeNode(8);
	// Testing
	nextNode(tree, 3);
	nextNode(tree, 7);
	nextNode(tree, 6);
	nextNode(tree, 5);
	nextNode(tree, 8);
	nextNode(tree, 1);
}

Output

 Node : 3
 Result : 6

 Node : 7
 Result : 8

 Node : 6
 Result : 5

 Node : 5
 Result : None

 Node : 8
 Result : 11

 Node : 1
 Result : None




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment