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 <iostream>
using namespace std;
/*
  C++ program for
  Find the next node of the key at the same 
  level in the binary tree
*/
// Binary Tree node
class TreeNode
{
	public: 
    int data;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int data)
	{
		// Set node value
		this->data = data;
		this->left = nullptr;
		this->right = nullptr;
	}
};
class BinaryTree
{
	public: 
    TreeNode *root;
	int status;
	TreeNode *result;
	BinaryTree()
	{
		this->root = nullptr;
		this->status = -1;
		this->result = nullptr;
	}
	// Method which are find next node of same level
	void findNextNode(TreeNode *temp, 
                      int level, 
                      int node)
	{
		if (temp != nullptr)
		{
			if (this->status == -1 && 
                temp->data == node)
			{
				// When found node value
				this->status = level;
			}
			else if (this->status == level && 
                     this->result == nullptr)
			{
				// Next node of same level
				this->result = temp;
			}
			// Visit to left subtree
			this->findNextNode(temp->left, 
                               level + 1, node);
			// Visit to right subtree
			this->findNextNode(temp->right,
                               level + 1, node);
		}
	}
	// This are handling the request of to finding next
	// node in same level by given node
	void nextNode(int node)
	{
		// Reset the result indicator
		this->status = -1;
		this->result = nullptr;
		// Find next node
		this->findNextNode(this->root, 0, node);
		cout << "\n Node : " << node << endl;
		cout << " Result : ";
		// Test Case
		if (this->status == -1)
		{
			// Case A
			// When node values are not exist
			cout << "Not found" << endl;
		}
		else if (this->result == nullptr)
		{
			// Case B
			// When next node is not found
			cout << "None" << endl;
		}
		else
		{
			// Case C
			// When next node are exist
			cout << this->result->data << endl;
		}
	}
};
int main()
{
	// Create new tree
	BinaryTree *tree = new BinaryTree();
	/*
	   Make A Binary Tree
	  ---------------------
	        1
	       / \ 
	      /   \ 
	     /     \
	    2       4
	   /       / \
	  /       /   \
	  3      6     5
	   \      \   /
	    7      8 11
	              
	*/
	// Add node in Binary Tree
	tree->root = new TreeNode(1);
	tree->root->left = new TreeNode(2);
	tree->root->left->left = new TreeNode(3);
	tree->root->left->left->right = new TreeNode(7);
	tree->root->right = new TreeNode(4);
	tree->root->right->right = new TreeNode(5);
	tree->root->right->right->left = new TreeNode(11);
	tree->root->right->left = new TreeNode(6);
	tree->root->right->left->right = new TreeNode(8);
	// Testing
	tree->nextNode(3);
	tree->nextNode(7);
	tree->nextNode(6);
	tree->nextNode(5);
	tree->nextNode(8);
	tree->nextNode(1);
	return 0;
}

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