Skip to main content

Sum of alternate leaf nodes in bst in c++

Sum of alternate leaf nodes

C++ program for Sum of alternate leaf nodes in bst. Here more information.

// Include header file
#include <iostream>
using namespace std;
// C++ program for
// Sum of alternate leaf nodes in bst
class TreeNode
{
	public: 
    int data;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int data)
	{
		this->data = data;
		this->left = nullptr;
		this->right = nullptr;
	}
};
class BinarySearchTree
{
	public: 
    TreeNode *root;
	bool alternate;
	BinarySearchTree()
	{
		this->root = nullptr;
		this->alternate = false;
	}
	// Insert a new node element
	void addNode(int data)
	{
		// Create a new node
		TreeNode *node = new TreeNode(data);
		if (this->root == nullptr)
		{
			// When add first node in bst
			this->root = node;
		}
		else
		{
			TreeNode *find = this->root;
			// Add new node to proper position
			while (find != nullptr)
			{
				if (find->data >= data)
				{
					if (find->left == nullptr)
					{
						// When left child empty
						// So add new node here
						find->left = node;
						return;
					}
					else
					{
						// Otherwise
						// Visit to left sub-tree
						find = find->left;
					}
				}
				else
				{
					if (find->right == nullptr)
					{
						// When right child empty
						// So add new node here
						find->right = node;
						return;
					}
					else
					{
						// Visit to right sub-tree
						find = find->right;
					}
				}
			}
		}
	}
	int leafSum(TreeNode *node)
	{
		if (node != nullptr)
		{
			if (node->left == nullptr && 
                node->right == nullptr)
			{
				// Case A
				// When node is leaf node
				// Change status
				this->alternate = !this->alternate;
				// Check node is alternate or not
				if (this->alternate)
				{
					// When get alternate node
					return node->data;
				}
			}
			else
			{
				// Case B
				// When node is internal
				// Visit left and right subtree and find alternate node
				return this->leafSum(node->left) + 
                       this->leafSum(node->right);
			}
		}
		return 0;
	}
	int alternateLeafSum()
	{
		// Reset alternate leaf node status
		this->alternate = false;
		return this->leafSum(this->root);
	}
};
int main()
{
	BinarySearchTree *tree = new BinarySearchTree();
	/*
		Binary search tree
	    -------------------
	       5
	      /  \  
	     /    \ 
	    /      \
	   3        19
	  / \     /   \
	 2   4   8     31
	       / \    / \
	      7   15 25  50  
	*/
	// Add tree node
	tree->addNode(5);
	tree->addNode(3);
	tree->addNode(19);
	tree->addNode(2);
	tree->addNode(4);
	tree->addNode(8);
	tree->addNode(31);
	tree->addNode(7);
	tree->addNode(25);
	tree->addNode(15);
	tree->addNode(50);
	// Test
	cout << tree->alternateLeafSum() << endl;
	return 0;
}

Output

34




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