# Sum of alternate leaf nodes in bst in c

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
// 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.