# Sum of alternate leaf nodes in bst in java

Java program for Sum of alternate leaf nodes in bst. Here problem description and explanation.

``````// Java program for
// Sum of alternate leaf nodes in bst
class TreeNode
{
public int data;
public TreeNode left, right;
public TreeNode(int data)
{
this.data = data;
this.left = null;
this.right = null;
}
}
public class BinarySearchTree
{
public TreeNode root;
public boolean alternate;
public BinarySearchTree()
{
this.root = null;
this.alternate = false;
}
// Insert a new node element
public void addNode(int data)
{
// Create a new node
TreeNode node = new TreeNode(data);
if (this.root == null)
{
// When add first node in bst
this.root = node;
}
else
{
TreeNode find = this.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;
}
}
}
}
}
public int leafSum(TreeNode node)
{
if (node != null)
{
if (node.left == null && node.right == null)
{
// 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 leafSum(node.left) +
leafSum(node.right);
}
}
return 0;
}
public int alternateLeafSum()
{
// Reset alternate leaf node status
this.alternate = false;
return leafSum(this.root);
}
public static void main(String[] args)
{
BinarySearchTree tree = new BinarySearchTree();
/*
Binary search tree
-------------------
5
/  \
/    \
/      \
3        19
/ \     /   \
2   4   8     31
/ \    / \
7   15 25  50

*/
// Add tree node
// Test
System.out.println(tree.alternateLeafSum());
}
}``````

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.