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 problem description and other solutions.

// Include header file
#include <stdio.h>
#include <stdlib.h>

// C program for
// Sum of alternate leaf nodes in bst
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;
	}
	ref->data = data;
	ref->left = NULL;
	ref->right = NULL;
	return ref;
}

typedef struct BinarySearchTree
{
	// Define useful field of BinarySearchTree
	struct TreeNode * root;
	int alternate;
}BinarySearchTree;

BinarySearchTree * getBinarySearchTree()
{
	// Create dynamic memory of BinarySearchTree
	BinarySearchTree * ref = 
	(BinarySearchTree * ) malloc(sizeof(BinarySearchTree));
	if (ref == NULL)
	{
		// Failed to create memory 
		return NULL;
	}
	ref->root = NULL;
	ref->alternate = 0;
	return ref;
}

// Insert a new node element
void addNode(BinarySearchTree * ref, int data)
{
	// Create a new node
	TreeNode * node = getTreeNode(data);
	if (ref->root == NULL)
	{
		// When add first node in bst
		ref->root = node;
	}
	else
	{
		TreeNode * find = ref->root;
		// Add new node to proper position
		while (find != NULL)
		{
			if (find->data >= data)
			{
				if (find->left == NULL)
				{
					// 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 == NULL)
				{
					// When right child empty
					// So add new node here
					find->right = node;
					return;
				}
				else
				{
					// Visit to right sub-tree
					find = find->right;
				}
			}
		}
	}
}

int leafSum(BinarySearchTree * ref, TreeNode * node)
{
	if (node != NULL)
	{
		if (node->left == NULL && node->right == NULL)
		{
			// Case A
			// When node is leaf node
			// Change status
			ref->alternate = !ref->alternate;
			// Check node is alternate or not
			if (ref->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 leafSum(ref,node->left) + 
			       leafSum(ref,node->right);
		}
	}
	return 0;
}
int alternateLeafSum(BinarySearchTree * ref)
{
	// Reset alternate leaf node status
	ref->alternate = 0;
	return leafSum(ref,ref->root);
}
int main()
{
	BinarySearchTree * tree = getBinarySearchTree();
	/*
		Binary search tree
	    -------------------
	       5
	      /  \  
	     /    \ 
	    /      \
	   3        19
	  / \     /   \
	 2   4   8     31
	       / \    / \
	      7   15 25  50  
	*/
	// Add tree node
	addNode(tree, 5);
	addNode(tree, 3);
	addNode(tree, 19);
	addNode(tree, 2);
	addNode(tree, 4);
	addNode(tree, 8);
	addNode(tree, 31);
	addNode(tree, 7);
	addNode(tree, 25);
	addNode(tree, 15);
	addNode(tree, 50);
	// Test
	printf("%d\n",alternateLeafSum(tree));
}

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