# Sum of alternate leaf nodes in bst in php

Php program for Sum of alternate leaf nodes in bst. Here mentioned other language solution.

``````<?php
// Php program for
// Sum of alternate leaf nodes in bst
class TreeNode
{
public \$data;
public \$left;
public \$right;
public	function __construct(\$data)
{
\$this->data = \$data;
\$this->left = NULL;
\$this->right = NULL;
}
}
class BinarySearchTree
{
public \$root;
public \$alternate;
public	function __construct()
{
\$this->root = NULL;
\$this->alternate = false;
}
// Insert a new node element
{
// Create a new node
\$node = new TreeNode(\$data);
if (\$this->root == NULL)
{
// When add first node in bst
\$this->root = \$node;
}
else
{
\$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	function leafSum(\$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 \$this->leafSum(\$node->left) +
\$this->leafSum(\$node->right);
}
}
return 0;
}
public	function alternateLeafSum()
{
// Reset alternate leaf node status
\$this->alternate = false;
return \$this->leafSum(\$this->root);
}
public static function main()
{
\$tree = new BinarySearchTree();
/*
Binary search tree
-------------------
5
/  \
/    \
/      \
3        19
/ \     /   \
2   4   8     31
/ \    / \
7   15 25  50
*/
// Test
printf("%d\n", \$tree->alternateLeafSum());
}
}
BinarySearchTree::main();``````

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.