# Find kth smallest element in BST php

Php program for Find kth smallest element in BST. Here mentioned other language solution.

``````<?php
// Php program for
// K’th smallest element in Binary Search Tree
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;
private \$counter;
private \$element;
public	function __construct()
{
\$this->root = NULL;
}
// Insert a node element
public	function insert(\$node, \$data)
{
if (\$node != NULL)
{
if (\$node->data >= \$data)
{
// When new element is smaller or equal to current node
\$node->left = \$this->insert(\$node->left, \$data);
}
else
{
// When new element is higher to current node
\$node->right = \$this->insert(\$node->right, \$data);
}
// Important to manage new node
return \$node;
}
else
{
return new TreeNode(\$data);
}
}
// Find the kth smallest node in BST
public	function findKthSmallest(\$node, \$k)
{
if (\$node != NULL)
{
// Visit left subtree
\$this->findKthSmallest(\$node->left, \$k);
if (\$this->counter == \$k)
{
// Stop recursion
return;
}
if (\$this->element == NULL ||
\$this->element->data < \$node->data)
{
// Modified counter variable by one
\$this->counter++;
// Collect possible result
\$this->element = \$node;
}
// Visit right subtree
\$this->findKthSmallest(\$node->right, \$k);
}
}
public	function printKthSsmallest(\$k)
{
if (\$k <= 0)
{
// When given k is not valid positive values
echo "Invalid node position ".strval(\$k), "\n";
}
else if (\$this->root == NULL)
{
// When BST are no have elements
echo "Empty Binary Search Tree\n";
}
else
{
// Reset values
\$this->counter = 0;
\$this->element = NULL;
// Find result
\$this->findKthSmallest(\$this->root, \$k);
if (\$this->counter < \$k)
{
// If In case given kth smallest node are
// Not exist in binary search tree, then
echo "Given ".strval(\$k)
." smallest node are not exist "
. strval(\$this->counter), "\n";
}
else
{
echo "[".strval(\$k).
"] smallest node : "
.strval(\$this->element->data), "\n";
}
}
}
// Handle request to add new node
{
\$this->root = \$this->insert(\$this->root, \$key);
}
public static function main()
{
\$tree = new BinarySearchTree();
/*
Make Tree
----------
7
/ \
/   \
4     9
/ \   / \
3   5 8   10
/
4
*/
// Testing
\$tree->printKthSsmallest(6);
\$tree->printKthSsmallest(4);
\$tree->printKthSsmallest(3);
}
}
BinarySearchTree::main();``````

Output

``````[6] smallest node : 9
[4] smallest node : 7
[3] smallest node : 5
``````

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