Skip to main content

Check if all leaf nodes are at same level in c++

C++ program for Check if all leaf nodes are at same level. Here problem description and explanation.

// Include header file
#include <iostream>
using namespace std;
/*
  C++ program for
  Check if all leaves are at same level 
*/
// 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 depth;
	BinaryTree()
	{
		this->root = nullptr;
		this->depth = -1;
	}
	void checkLeafHeight(TreeNode *node, int level)
	{
		if (node != nullptr)
		{
			// Test node is leaf or not
			if (node->left == nullptr && 
                node->right == nullptr)
			{
				if (this->depth == -1)
				{
					// This is first leaf node
					// Get node level
					this->depth = level;
				}
				else if (this->depth != level)
				{
					// When two leaf nodes is different level
					this->depth = -2;
					return;
				}
			}
			if (this->depth != -2)
			{
				// Recursively visit left and right subtree
				this->checkLeafHeight(node->left, level + 1);
				this->checkLeafHeight(node->right, level + 1);
			}
		}
	}
	void isSameLevelLeaf()
	{
		this->depth = -1;
		// Test
		this->checkLeafHeight(this->root, 1);
		// Display result
		if (this->depth < 0)
		{
			// Two possible case
			// 1) When tree empty
			// 2) When leaf node are not same level
			cout << "No" << endl;
		}
		else
		{
			// When leaf node is same level
			cout << "Yes" << endl;
		}
	}
};
int main()
{
	// Create new tree
	BinaryTree *tree = new BinaryTree();
	/* 
	    Make A Binary Tree
	    --------------------
	      1
	     /  \
	    2    3
	   /    /  \
	  4    5    6
	       
	*/
	//insertion of binary Tree nodes
	tree->root = new TreeNode(1);
	tree->root->left = new TreeNode(2);
	tree->root->right = new TreeNode(3);
	tree->root->right->right = new TreeNode(6);
	tree->root->right->left = new TreeNode(5);
	tree->root->left->left = new TreeNode(4);
	tree->isSameLevelLeaf();
	// Add new node
	tree->root->left->left->left = new TreeNode(7);
	/*
	   When add new node
	    -----------------------
	          1
	         /  \
	        2    3
	       /    /  \
	      4    5    6
	     /
	    7  
	*/
	tree->isSameLevelLeaf();
	return 0;
}

Output

Yes
No




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