Kth smallest element in a perfect binary search tree

Here given code implementation process.

// C program for
// Kth smallest element in a perfect binary search tree
#include <stdio.h>
#include <stdlib.h>

 // Tree Node
struct TreeNode
{
	int data;
	struct TreeNode *left;
	struct TreeNode *right;
};

// Binary search tree
struct BST
{
	struct TreeNode *root;
};
// Create new tree
struct BST *newTree()
{
	// Create a dynamic tree 
	struct BST *tree = (struct BST *) malloc(sizeof(struct BST));
	if (tree != NULL)
	{
		tree->root = NULL;
	}
	else
	{
		printf("Memory Overflow to Create tree Tree\n");
	}
	// return new tree
	return tree;
}
// This is creates and returns the new binary tree node
struct TreeNode *getNode(int data)
{
	// Create dynamic node
	struct TreeNode *node = 
      (struct TreeNode *) malloc(sizeof(struct TreeNode));
	if (node != NULL)
	{
		//Set data and pointer values
		node->data = data;
		node->left = NULL;
		node->right = NULL;
	}
	else
	{
		//This is indicates, segmentation fault or memory overflow problem
		printf("Memory Overflow\n");
	}
	//return new node
	return node;
}
// Adding a new node in binary search tree
void addNode(struct BST *tree, int data)
{
	struct TreeNode *node = getNode(data);
	if (node != NULL)
	{
		if (tree->root == NULL)
		{
			tree->root = node;
		}
		else
		{
			struct TreeNode *auxiliary = tree->root;
			// Add new node in binary search tree
			while (auxiliary != NULL)
			{
				if (data > auxiliary->data)
				{
					if (auxiliary->right == NULL)
					{
						// Add new node at right child
						auxiliary->right = node;
						return;
					}
					auxiliary = auxiliary->right;
				}
				else
				{
					if (auxiliary->left == NULL)
					{
						// Add new node at left child
						auxiliary->left = node;
						return;
					}
					auxiliary = auxiliary->left;
				}
			}
		}
	}
}
// Count number of nodes in binary tree
int countNode(struct TreeNode *node)
{
	if (node == NULL)
	{
		return 0;
	}
	return countNode(node->left) + countNode(node->right) + 1;
}
struct TreeNode *findKthSmallestNode(struct TreeNode *node, int k, int n)
{
	if (node == NULL)
	{
		return NULL;
	}
	int mid = (n / 2) + 1;
	if (mid == k)
	{
		// Get resultant node
		return node;
	}
	if (k < mid)
	{
		return findKthSmallestNode(node->left, k, mid - 1);
	}
	else
	{
		return findKthSmallestNode(node->right, k - mid, mid - 1);
	}
}
void printInorder(struct TreeNode *node)
{
	if (node != NULL)
	{
		printInorder(node->left);
		printf("  %d", node->data);
		printInorder(node->right);
	}
}
void kthSmallestNode(struct TreeNode *node, int k)
{
	if (node == NULL)
	{
		// When empty tree
		return;
	}
	// Count number of nodes in binary tree
	int n = countNode(node);
	if (k <= 0 || n < k)
	{
		// Invalid k
		return;
	}
	// Find kth smallest
	struct TreeNode *result = findKthSmallestNode(node, k, n);
	// Display calculated result
	printf("\n (%d)-th smallest is : %d", k, result->data);
}
int main(int argc, char
	const *argv[])
{
	struct BST *tree = newTree();
	/*
	              10 
	             /  \
	            /    \
	           /      \ 
	          /        \
	         /          \                           
	        /            \    
	       4               25    
	      /  \            /  \   
	     /    \          /    \      
	    2       7       19     29
	   / \     / \     / \     / \ 
	  /   \   /   \   /   \   /   \
	 -1    3 6     8 12   21 27   34 
	
	-----------------
	  Constructing binary search tree
	*/
	addNode(tree, 10);
	addNode(tree, 4);
	addNode(tree, 2);
	addNode(tree, -1);
	addNode(tree, 3);
	addNode(tree, 7);
	addNode(tree, 6);
	addNode(tree, 8);
	addNode(tree, 25);
	addNode(tree, 19);
	addNode(tree, 12);
	addNode(tree, 21);
	addNode(tree, 29);
	addNode(tree, 27);
	addNode(tree, 34);
	// Print tree element
	printInorder(tree->root);
	// Test Cases
	kthSmallestNode(tree->root, 4);
	kthSmallestNode(tree->root, 8);
	kthSmallestNode(tree->root, 5);
	kthSmallestNode(tree->root, 1);
	kthSmallestNode(tree->root, 14);
	return 0;
}

input

  -1  2  3  4  6  7  8  10  12  19  21  25  27  29  34
 (4)-th smallest is : 4
 (8)-th smallest is : 10
 (5)-th smallest is : 6
 (1)-th smallest is : -1
 (14)-th smallest is : 29
// Java program
// Kth smallest element in a perfect binary search tree
class TreeNode
{
	// Data value 
	public int data;
	// Indicates left and right subtree
	public TreeNode left;
	public TreeNode right;
	public TreeNode(int data)
	{
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
public class BinarySearchTree
{
	public TreeNode root;
	public BinarySearchTree()
	{
		this.root = null;
	}
	// Print the inorder of binary tree nodes
	public void printInorder(TreeNode node)
	{
		if (node != null)
		{
			printInorder(node.left);
			//print node value
			System.out.print("  " + node.data);
			printInorder(node.right);
		}
	}
	// insert a node in BST
	public void addNode(int data)
	{
		// Create new node of tree
		TreeNode node = new TreeNode(data);
		if (this.root == null)
		{
			this.root = node;
		}
		else
		{
			TreeNode auxiliary = this.root;
			// Add new node in binary search tree
			while (auxiliary != null)
			{
				if (data > auxiliary.data)
				{
					if (auxiliary.right == null)
					{
						// Add new node at right child
						auxiliary.right = node;
						return;
					}
					auxiliary = auxiliary.right;
				}
				else
				{
					if (auxiliary.left == null)
					{
						// Add new node at left child
						auxiliary.left = node;
						return;
					}
					auxiliary = auxiliary.left;
				}
			}
		}
	}
	// Count number of nodes in binary tree
	public int countNode(TreeNode node)
	{
		if (node == null)
		{
			return 0;
		}
		return countNode(node.left) + countNode(node.right) + 1;
	}
	public TreeNode findKthSmallestNode(TreeNode node, int k, int n)
	{
		if (node == null)
		{
			return null;
		}
		int mid = (n / 2) + 1;
		if (mid == k)
		{
			// Get resultant node
			return node;
		}
		if (k < mid)
		{
			return findKthSmallestNode(node.left, k, mid - 1);
		}
		else
		{
			return findKthSmallestNode(node.right, k - mid, mid - 1);
		}
	}
	public void kthSmallestNode(int k)
	{
		if (this.root == null)
		{
			// When empty tree
			return;
		}
		// Count number of nodes in binary tree
		int n = countNode(this.root);
		if (k <= 0 || n < k)
		{
			// Invalid k
			return;
		}
		// Find kth smallest
		TreeNode result = findKthSmallestNode(this.root, k, n);
		// Display calculated result
		System.out.print("\n (" + k + ")-th smallest is : " + result.data);
	}
	public static void main(String[] args)
	{
		BinarySearchTree tree = new BinarySearchTree();
		/*
		              10 
		             /  \
		            /    \
		           /      \ 
		          /        \
		         /          \                           
		        /            \    
		       4               25    
		      /  \            /  \   
		     /    \          /    \      
		    2       7       19     29
		   / \     / \     / \     / \ 
		  /   \   /   \   /   \   /   \
		 -1    3 6     8 12   21 27   34 
		-----------------
		  Constructing binary search tree
		*/
		tree.addNode(10);
		tree.addNode(4);
		tree.addNode(2);
		tree.addNode(-1);
		tree.addNode(3);
		tree.addNode(7);
		tree.addNode(6);
		tree.addNode(8);
		tree.addNode(25);
		tree.addNode(19);
		tree.addNode(12);
		tree.addNode(21);
		tree.addNode(29);
		tree.addNode(27);
		tree.addNode(34);
		// Print tree element
		tree.printInorder(tree.root);
		// Test Cases
		tree.kthSmallestNode(4);
		tree.kthSmallestNode(8);
		tree.kthSmallestNode(5);
		tree.kthSmallestNode(1);
		tree.kthSmallestNode(14);
	}
}

input

  -1  2  3  4  6  7  8  10  12  19  21  25  27  29  34
 (4)-th smallest is : 4
 (8)-th smallest is : 10
 (5)-th smallest is : 6
 (1)-th smallest is : -1
 (14)-th smallest is : 29
// Include header file
#include <iostream>
using namespace std;
// C++ program
// Kth smallest element in a perfect binary search tree

class TreeNode
{
	public:
	// Data value
	int data;
	// Indicates left and right subtree
	TreeNode *left;
	TreeNode *right;
	TreeNode(int data)
	{
		this->data = data;
		this->left = NULL;
		this->right = NULL;
	}
};
class BinarySearchTree
{
	public: TreeNode *root;
	BinarySearchTree()
	{
		this->root = NULL;
	}
	// Print the inorder of binary tree nodes
	void printInorder(TreeNode *node)
	{
		if (node != NULL)
		{
			this->printInorder(node->left);
			//print node value
			cout << "  " << node->data;
			this->printInorder(node->right);
		}
	}
	// insert a node in BST
	void addNode(int data)
	{
		// Create new node of tree
		TreeNode *node = new TreeNode(data);
		if (this->root == NULL)
		{
			this->root = node;
		}
		else
		{
			TreeNode *auxiliary = this->root;
			// Add new node in binary search tree
			while (auxiliary != NULL)
			{
				if (data > auxiliary->data)
				{
					if (auxiliary->right == NULL)
					{
						// Add new node at right child
						auxiliary->right = node;
						return;
					}
					auxiliary = auxiliary->right;
				}
				else
				{
					if (auxiliary->left == NULL)
					{
						// Add new node at left child
						auxiliary->left = node;
						return;
					}
					auxiliary = auxiliary->left;
				}
			}
		}
	}
	// Count number of nodes in binary tree
	int countNode(TreeNode *node)
	{
		if (node == NULL)
		{
			return 0;
		}
		return this->countNode(node->left) + this->countNode(node->right) + 1;
	}
	TreeNode *findKthSmallestNode(TreeNode *node, int k, int n)
	{
		if (node == NULL)
		{
			return NULL;
		}
		int mid = (n / 2) + 1;
		if (mid == k)
		{
			// Get resultant node
			return node;
		}
		if (k < mid)
		{
			return this->findKthSmallestNode(node->left, k, mid - 1);
		}
		else
		{
			return this->findKthSmallestNode(node->right, k - mid, mid - 1);
		}
	}
	void kthSmallestNode(int k)
	{
		if (this->root == NULL)
		{
			// When empty tree
			return;
		}
		// Count number of nodes in binary tree
		int n = this->countNode(this->root);
		if (k <= 0 || n < k)
		{
			// Invalid k
			return;
		}
		// Find kth smallest
		TreeNode *result = this->findKthSmallestNode(this->root, k, n);
		// Display calculated result
		cout << "\n (" << k << ")-th smallest is : " << result->data;
	}
};
int main()
{
	BinarySearchTree *tree = new BinarySearchTree();
	/*
	              10 
	             /  \
	            /    \
	           /      \ 
	          /        \
	         /          \                           
	        /            \    
	       4               25    
	      /  \            /  \   
	     /    \          /    \      
	    2       7       19     29
	   / \     / \     / \     / \ 
	  /   \   /   \   /   \   /   \
	 -1    3 6     8 12   21 27   34 
	-----------------
	  Constructing binary search tree
	*/
	tree->addNode(10);
	tree->addNode(4);
	tree->addNode(2);
	tree->addNode(-1);
	tree->addNode(3);
	tree->addNode(7);
	tree->addNode(6);
	tree->addNode(8);
	tree->addNode(25);
	tree->addNode(19);
	tree->addNode(12);
	tree->addNode(21);
	tree->addNode(29);
	tree->addNode(27);
	tree->addNode(34);
	// Print tree element
	tree->printInorder(tree->root);
	// Test Cases
	tree->kthSmallestNode(4);
	tree->kthSmallestNode(8);
	tree->kthSmallestNode(5);
	tree->kthSmallestNode(1);
	tree->kthSmallestNode(14);
	return 0;
}

input

  -1  2  3  4  6  7  8  10  12  19  21  25  27  29  34
 (4)-th smallest is : 4
 (8)-th smallest is : 10
 (5)-th smallest is : 6
 (1)-th smallest is : -1
 (14)-th smallest is : 29
// Include namespace system
using System;
// Csharp program
// Kth smallest element in a perfect binary search tree
public class TreeNode
{
	// Data value
	public int data;
	// Indicates left and right subtree
	public TreeNode left;
	public TreeNode right;
	public TreeNode(int data)
	{
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
public class BinarySearchTree
{
	public TreeNode root;
	public BinarySearchTree()
	{
		this.root = null;
	}
	// Print the inorder of binary tree nodes
	public void printInorder(TreeNode node)
	{
		if (node != null)
		{
			this.printInorder(node.left);
			//print node value
			Console.Write("  " + node.data);
			this.printInorder(node.right);
		}
	}
	// insert a node in BST
	public void addNode(int data)
	{
		// Create new node of tree
		TreeNode node = new TreeNode(data);
		if (this.root == null)
		{
			this.root = node;
		}
		else
		{
			TreeNode auxiliary = this.root;
			// Add new node in binary search tree
			while (auxiliary != null)
			{
				if (data > auxiliary.data)
				{
					if (auxiliary.right == null)
					{
						// Add new node at right child
						auxiliary.right = node;
						return;
					}
					auxiliary = auxiliary.right;
				}
				else
				{
					if (auxiliary.left == null)
					{
						// Add new node at left child
						auxiliary.left = node;
						return;
					}
					auxiliary = auxiliary.left;
				}
			}
		}
	}
	// Count number of nodes in binary tree
	public int countNode(TreeNode node)
	{
		if (node == null)
		{
			return 0;
		}
		return this.countNode(node.left) + this.countNode(node.right) + 1;
	}
	public TreeNode findKthSmallestNode(TreeNode node, int k, int n)
	{
		if (node == null)
		{
			return null;
		}
		int mid = (n / 2) + 1;
		if (mid == k)
		{
			// Get resultant node
			return node;
		}
		if (k < mid)
		{
			return this.findKthSmallestNode(node.left, k, mid - 1);
		}
		else
		{
			return this.findKthSmallestNode(node.right, k - mid, mid - 1);
		}
	}
	public void kthSmallestNode(int k)
	{
		if (this.root == null)
		{
			// When empty tree
			return;
		}
		// Count number of nodes in binary tree
		int n = this.countNode(this.root);
		if (k <= 0 || n < k)
		{
			// Invalid k
			return;
		}
		// Find kth smallest
		TreeNode result = this.findKthSmallestNode(this.root, k, n);
		// Display calculated result
		Console.Write("\n (" + k + ")-th smallest is : " + result.data);
	}
	public static void Main(String[] args)
	{
		BinarySearchTree tree = new BinarySearchTree();
		/*
		              10 
		             /  \
		            /    \
		           /      \ 
		          /        \
		         /          \                           
		        /            \    
		       4               25    
		      /  \            /  \   
		     /    \          /    \      
		    2       7       19     29
		   / \     / \     / \     / \ 
		  /   \   /   \   /   \   /   \
		 -1    3 6     8 12   21 27   34 
		-----------------
		  Constructing binary search tree
		*/
		tree.addNode(10);
		tree.addNode(4);
		tree.addNode(2);
		tree.addNode(-1);
		tree.addNode(3);
		tree.addNode(7);
		tree.addNode(6);
		tree.addNode(8);
		tree.addNode(25);
		tree.addNode(19);
		tree.addNode(12);
		tree.addNode(21);
		tree.addNode(29);
		tree.addNode(27);
		tree.addNode(34);
		// Print tree element
		tree.printInorder(tree.root);
		// Test Cases
		tree.kthSmallestNode(4);
		tree.kthSmallestNode(8);
		tree.kthSmallestNode(5);
		tree.kthSmallestNode(1);
		tree.kthSmallestNode(14);
	}
}

input

  -1  2  3  4  6  7  8  10  12  19  21  25  27  29  34
 (4)-th smallest is : 4
 (8)-th smallest is : 10
 (5)-th smallest is : 6
 (1)-th smallest is : -1
 (14)-th smallest is : 29
<?php
// Php program
// Kth smallest element in a perfect binary search tree
class TreeNode
{
	// Data value
	public $data;
	// Indicates left and right subtree
	public $left;
	public $right;
	public	function __construct($data)
	{
		$this->data = $data;
		$this->left = NULL;
		$this->right = NULL;
	}
}
class BinarySearchTree
{
	public $root;
	public	function __construct()
	{
		$this->root = NULL;
	}
	// Print the inorder of binary tree nodes
	public	function printInorder($node)
	{
		if ($node != NULL)
		{
			$this->printInorder($node->left);
			//print node value
			echo("  ".$node->data);
			$this->printInorder($node->right);
		}
	}
	// insert a node in BST
	public	function addNode($data)
	{
		// Create new node of tree
		$node = new TreeNode($data);
		if ($this->root == NULL)
		{
			$this->root = $node;
		}
		else
		{
			$auxiliary = $this->root;
			// Add new node in binary search tree
			while ($auxiliary != NULL)
			{
				if ($data > $auxiliary->data)
				{
					if ($auxiliary->right == NULL)
					{
						// Add new node at right child
						$auxiliary->right = $node;
						return;
					}
					$auxiliary = $auxiliary->right;
				}
				else
				{
					if ($auxiliary->left == NULL)
					{
						// Add new node at left child
						$auxiliary->left = $node;
						return;
					}
					$auxiliary = $auxiliary->left;
				}
			}
		}
	}
	// Count number of nodes in binary tree
	public	function countNode($node)
	{
		if ($node == NULL)
		{
			return 0;
		}
		return $this->countNode($node->left) + $this->countNode($node->right) + 1;
	}
	public	function findKthSmallestNode($node, $k, $n)
	{
		if ($node == NULL)
		{
			return NULL;
		}
		$mid = ((int)($n / 2)) + 1;
		if ($mid == $k)
		{
			// Get resultant node
			return $node;
		}
		if ($k < $mid)
		{
			return $this->findKthSmallestNode($node->left, 
                                              $k, $mid - 1);
		}
		else
		{
			return $this->findKthSmallestNode($node->right, 
                                              $k - $mid, $mid - 1);
		}
	}
	public	function kthSmallestNode($k)
	{
		if ($this->root == NULL)
		{
			// When empty tree
			return;
		}
		// Count number of nodes in binary tree
		$n = $this->countNode($this->root);
		if ($k <= 0 || $n < $k)
		{
			// Invalid k
			return;
		}
		// Find kth smallest
		$result = $this->findKthSmallestNode($this->root, $k, $n);
		// Display calculated result
		echo("\n (".$k.
			")-th smallest is : ".$result->data);
	}
}

function main()
{
	$tree = new BinarySearchTree();
	/*
	              10 
	             /  \
	            /    \
	           /      \ 
	          /        \
	         /          \                           
	        /            \    
	       4               25    
	      /  \            /  \   
	     /    \          /    \      
	    2       7       19     29
	   / \     / \     / \     / \ 
	  /   \   /   \   /   \   /   \
	 -1    3 6     8 12   21 27   34 
	-----------------
	  Constructing binary search tree
	*/
	$tree->addNode(10);
	$tree->addNode(4);
	$tree->addNode(2);
	$tree->addNode(-1);
	$tree->addNode(3);
	$tree->addNode(7);
	$tree->addNode(6);
	$tree->addNode(8);
	$tree->addNode(25);
	$tree->addNode(19);
	$tree->addNode(12);
	$tree->addNode(21);
	$tree->addNode(29);
	$tree->addNode(27);
	$tree->addNode(34);
	// Print tree element
	$tree->printInorder($tree->root);
	// Test Cases
	$tree->kthSmallestNode(4);
	$tree->kthSmallestNode(8);
	$tree->kthSmallestNode(5);
	$tree->kthSmallestNode(1);
	$tree->kthSmallestNode(14);
}
main();

input

  -1  2  3  4  6  7  8  10  12  19  21  25  27  29  34
 (4)-th smallest is : 4
 (8)-th smallest is : 10
 (5)-th smallest is : 6
 (1)-th smallest is : -1
 (14)-th smallest is : 29
// Node JS program
// Kth smallest element in a perfect binary search tree
class TreeNode
{
	constructor(data)
	{
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
class BinarySearchTree
{
	constructor()
	{
		this.root = null;
	}
	// Print the inorder of binary tree nodes
	printInorder(node)
	{
		if (node != null)
		{
			this.printInorder(node.left);
			//print node value
			process.stdout.write("  " + node.data);
			this.printInorder(node.right);
		}
	}
	// insert a node in BST
	addNode(data)
	{
		// Create new node of tree
		var node = new TreeNode(data);
		if (this.root == null)
		{
			this.root = node;
		}
		else
		{
			var auxiliary = this.root;
			// Add new node in binary search tree
			while (auxiliary != null)
			{
				if (data > auxiliary.data)
				{
					if (auxiliary.right == null)
					{
						// Add new node at right child
						auxiliary.right = node;
						return;
					}
					auxiliary = auxiliary.right;
				}
				else
				{
					if (auxiliary.left == null)
					{
						// Add new node at left child
						auxiliary.left = node;
						return;
					}
					auxiliary = auxiliary.left;
				}
			}
		}
	}
	// Count number of nodes in binary tree
	countNode(node)
	{
		if (node == null)
		{
			return 0;
		}
		return this.countNode(node.left) + this.countNode(node.right) + 1;
	}
	findKthSmallestNode(node, k, n)
	{
		if (node == null)
		{
			return null;
		}
		var mid = (parseInt(n / 2)) + 1;
		if (mid == k)
		{
			// Get resultant node
			return node;
		}
		if (k < mid)
		{
			return this.findKthSmallestNode(node.left, k, mid - 1);
		}
		else
		{
			return this.findKthSmallestNode(node.right, k - mid, mid - 1);
		}
	}
	kthSmallestNode(k)
	{
		if (this.root == null)
		{
			// When empty tree
			return;
		}
		// Count number of nodes in binary tree
		var n = this.countNode(this.root);
		if (k <= 0 || n < k)
		{
			// Invalid k
			return;
		}
		// Find kth smallest
		var result = this.findKthSmallestNode(this.root, k, n);
		// Display calculated result
		process.stdout.write("\n (" + k + ")-th smallest is : " + result.data);
	}
}

function main()
{
	var tree = new BinarySearchTree();
	/*
	              10 
	             /  \
	            /    \
	           /      \ 
	          /        \
	         /          \                           
	        /            \    
	       4               25    
	      /  \            /  \   
	     /    \          /    \      
	    2       7       19     29
	   / \     / \     / \     / \ 
	  /   \   /   \   /   \   /   \
	 -1    3 6     8 12   21 27   34 
	-----------------
	  Constructing binary search tree
	*/
	tree.addNode(10);
	tree.addNode(4);
	tree.addNode(2);
	tree.addNode(-1);
	tree.addNode(3);
	tree.addNode(7);
	tree.addNode(6);
	tree.addNode(8);
	tree.addNode(25);
	tree.addNode(19);
	tree.addNode(12);
	tree.addNode(21);
	tree.addNode(29);
	tree.addNode(27);
	tree.addNode(34);
	// Print tree element
	tree.printInorder(tree.root);
	// Test Cases
	tree.kthSmallestNode(4);
	tree.kthSmallestNode(8);
	tree.kthSmallestNode(5);
	tree.kthSmallestNode(1);
	tree.kthSmallestNode(14);
}
main();

input

  -1  2  3  4  6  7  8  10  12  19  21  25  27  29  34
 (4)-th smallest is : 4
 (8)-th smallest is : 10
 (5)-th smallest is : 6
 (1)-th smallest is : -1
 (14)-th smallest is : 29
#  Python 3 program
#  Kth smallest element in a perfect binary search tree
class TreeNode :
	#  Data value
	#  Indicates left and right subtree
	def __init__(self, data) :
		self.data = data
		self.left = None
		self.right = None
	

class BinarySearchTree :
	def __init__(self) :
		self.root = None
	
	#  Print the inorder of binary tree nodes
	def printInorder(self, node) :
		if (node != None) :
			self.printInorder(node.left)
			# print node value
			print("  ", node.data, end = "")
			self.printInorder(node.right)
		
	
	#  insert a node in BST
	def addNode(self, data) :
		#  Create new node of tree
		node = TreeNode(data)
		if (self.root == None) :
			self.root = node
		else :
			auxiliary = self.root
			#  Add new node in binary search tree
			while (auxiliary != None) :
				if (data > auxiliary.data) :
					if (auxiliary.right == None) :
						#  Add new node at right child
						auxiliary.right = node
						return
					
					auxiliary = auxiliary.right
				else :
					if (auxiliary.left == None) :
						#  Add new node at left child
						auxiliary.left = node
						return
					
					auxiliary = auxiliary.left
				
			
		
	
	#  Count number of nodes in binary tree
	def countNode(self, node) :
		if (node == None) :
			return 0
		
		return self.countNode(node.left) + self.countNode(node.right) + 1
	
	def findKthSmallestNode(self, node, k, n) :
		if (node == None) :
			return None
		
		mid = (int(n / 2)) + 1
		if (mid == k) :
			#  Get resultant node
			return node
		
		if (k < mid) :
			return self.findKthSmallestNode(node.left, k, mid - 1)
		else :
			return self.findKthSmallestNode(node.right, k - mid, mid - 1)
		
	
	def kthSmallestNode(self, k) :
		if (self.root == None) :
			#  When empty tree
			return
		
		#  Count number of nodes in binary tree
		n = self.countNode(self.root)
		if (k <= 0 or n < k) :
			#  Invalid k
			return
		
		#  Find kth smallest
		result = self.findKthSmallestNode(self.root, k, n)
		#  Display calculated result
		print("\n (", k ,")-th smallest is : ", result.data, end = "")
	

def main() :
	tree = BinarySearchTree()
	#              10 
	#             /  \
	#            /    \
	#           /      \ 
	#          /        \
	#         /          \                           
	#        /            \    
	#       4               25    
	#      /  \            /  \   
	#     /    \          /    \      
	#    2       7       19     29
	#   / \     / \     / \     / \ 
	#  /   \   /   \   /   \   /   \
	# -1    3 6     8 12   21 27   34 
	# -----------------
	#  Constructing binary search tree
	tree.addNode(10)
	tree.addNode(4)
	tree.addNode(2)
	tree.addNode(-1)
	tree.addNode(3)
	tree.addNode(7)
	tree.addNode(6)
	tree.addNode(8)
	tree.addNode(25)
	tree.addNode(19)
	tree.addNode(12)
	tree.addNode(21)
	tree.addNode(29)
	tree.addNode(27)
	tree.addNode(34)
	#  Print tree element
	tree.printInorder(tree.root)
	#  Test Cases
	tree.kthSmallestNode(4)
	tree.kthSmallestNode(8)
	tree.kthSmallestNode(5)
	tree.kthSmallestNode(1)
	tree.kthSmallestNode(14)

if __name__ == "__main__": main()

input

   -1   2   3   4   6   7   8   10   12   19   21   25   27   29   34
 ( 4 )-th smallest is :  4
 ( 8 )-th smallest is :  10
 ( 5 )-th smallest is :  6
 ( 1 )-th smallest is :  -1
 ( 14 )-th smallest is :  29
#  Ruby program
#  Kth smallest element in a perfect binary search tree
class TreeNode 
	# Define the accessor and reader of class TreeNode
	attr_reader :data, :left, :right
	attr_accessor :data, :left, :right
	#  Data value
	#  Indicates left and right subtree
	def initialize(data) 
		self.data = data
		self.left = nil
		self.right = nil
	end
end

class BinarySearchTree 
	# Define the accessor and reader of class BinarySearchTree
	attr_reader :root
	attr_accessor :root
	def initialize() 
		self.root = nil
	end

	#  Print the inorder of binary tree nodes
	def printInorder(node) 
		if (node != nil) 
			self.printInorder(node.left)
			# print node value
			print("  ", node.data)
			self.printInorder(node.right)
		end

	end

	#  insert a node in BST
	def addNode(data) 
		#  Create new node of tree
		node = TreeNode.new(data)
		if (self.root == nil) 
			self.root = node
		else
 
			auxiliary = self.root
			#  Add new node in binary search tree
			while (auxiliary != nil) 
				if (data > auxiliary.data) 
					if (auxiliary.right == nil) 
						#  Add new node at right child
						auxiliary.right = node
						return
					end

					auxiliary = auxiliary.right
				else
					if (auxiliary.left == nil) 
						#  Add new node at left child
						auxiliary.left = node
						return
					end

					auxiliary = auxiliary.left
				end

			end

		end

	end

	#  Count number of nodes in binary tree
	def countNode(node) 
		if (node == nil) 
			return 0
		end

		return self.countNode(node.left) + self.countNode(node.right) + 1
	end

	def findKthSmallestNode(node, k, n) 
		if (node == nil) 
			return nil
		end

		mid = (n / 2) + 1
		if (mid == k) 
			#  Get resultant node
			return node
		end

		if (k < mid) 
			return self.findKthSmallestNode(node.left, k, mid - 1)
		else
 
			return self.findKthSmallestNode(node.right, k - mid, mid - 1)
		end

	end

	def kthSmallestNode(k) 
		if (self.root == nil) 
			#  When empty tree
			return
		end

		#  Count number of nodes in binary tree
		n = self.countNode(self.root)
		if (k <= 0 || n < k) 
			#  Invalid k
			return
		end

		#  Find kth smallest
		result = self.findKthSmallestNode(self.root, k, n)
		#  Display calculated result
		print("\n (", k ,")-th smallest is : ", result.data)
	end

end

def main() 
	tree = BinarySearchTree.new()
	#              10 
	#             /  \
	#            /    \
	#           /      \ 
	#          /        \
	#         /          \                           
	#        /            \    
	#       4               25    
	#      /  \            /  \   
	#     /    \          /    \      
	#    2       7       19     29
	#   / \     / \     / \     / \ 
	#  /   \   /   \   /   \   /   \
	# -1    3 6     8 12   21 27   34 
	# -----------------
	#  Constructing binary search tree
	tree.addNode(10)
	tree.addNode(4)
	tree.addNode(2)
	tree.addNode(-1)
	tree.addNode(3)
	tree.addNode(7)
	tree.addNode(6)
	tree.addNode(8)
	tree.addNode(25)
	tree.addNode(19)
	tree.addNode(12)
	tree.addNode(21)
	tree.addNode(29)
	tree.addNode(27)
	tree.addNode(34)
	#  Print tree element
	tree.printInorder(tree.root)
	#  Test Cases
	tree.kthSmallestNode(4)
	tree.kthSmallestNode(8)
	tree.kthSmallestNode(5)
	tree.kthSmallestNode(1)
	tree.kthSmallestNode(14)
end

main()

input

  -1  2  3  4  6  7  8  10  12  19  21  25  27  29  34
 (4)-th smallest is : 4
 (8)-th smallest is : 10
 (5)-th smallest is : 6
 (1)-th smallest is : -1
 (14)-th smallest is : 29
// Scala program
// Kth smallest element in a perfect binary search tree
class TreeNode(
	// Data value
	var data: Int,
		// Indicates left and right subtree
		var left: TreeNode,
			var right: TreeNode)
{
	def this(data: Int)
	{
		this(data,null,null);
	}
}
class BinarySearchTree(var root: TreeNode)
{
	def this()
	{
		this(null);
	}
	// Print the inorder of binary tree nodes
	def printInorder(node: TreeNode): Unit = {
		if (node != null)
		{
			printInorder(node.left);
			//print node value
			print("  " + node.data);
			printInorder(node.right);
		}
	}
	// insert a node in BST
	def addNode(data: Int): Unit = {
		// Create new node of tree
		var node: TreeNode = new TreeNode(data);
		if (this.root == null)
		{
			this.root = node;
		}
		else
		{
			var auxiliary: TreeNode = this.root;
			// Add new node in binary search tree
			while (auxiliary != null)
			{
				if (data > auxiliary.data)
				{
					if (auxiliary.right == null)
					{
						// Add new node at right child
						auxiliary.right = node;
						return;
					}
					auxiliary = auxiliary.right;
				}
				else
				{
					if (auxiliary.left == null)
					{
						// Add new node at left child
						auxiliary.left = node;
						return;
					}
					auxiliary = auxiliary.left;
				}
			}
		}
	}
	// Count number of nodes in binary tree
	def countNode(node: TreeNode): Int = {
		if (node == null)
		{
			return 0;
		}
		return countNode(node.left) + countNode(node.right) + 1;
	}
	def findKthSmallestNode(node: TreeNode, k: Int, n: Int): TreeNode = {
		if (node == null)
		{
			return null;
		}
		var mid: Int = (n / 2) + 1;
		if (mid == k)
		{
			// Get resultant node
			return node;
		}
		if (k < mid)
		{
			return findKthSmallestNode(node.left, k, mid - 1);
		}
		else
		{
			return findKthSmallestNode(node.right, k - mid, mid - 1);
		}
	}
	def kthSmallestNode(k: Int): Unit = {
		if (this.root == null)
		{
			// When empty tree
			return;
		}
		// Count number of nodes in binary tree
		var n: Int = countNode(this.root);
		if (k <= 0 || n < k)
		{
			// Invalid k
			return;
		}
		// Find kth smallest
		var result: TreeNode = findKthSmallestNode(this.root, k, n);
		// Display calculated result
		print("\n (" + k + ")-th smallest is : " + result.data);
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var tree: BinarySearchTree = new BinarySearchTree();
		/*
		              10 
		             /  \
		            /    \
		           /      \ 
		          /        \
		         /          \                           
		        /            \    
		       4               25    
		      /  \            /  \   
		     /    \          /    \      
		    2       7       19     29
		   / \     / \     / \     / \ 
		  /   \   /   \   /   \   /   \
		 -1    3 6     8 12   21 27   34 
		-----------------
		  Constructing binary search tree
		*/
		tree.addNode(10);
		tree.addNode(4);
		tree.addNode(2);
		tree.addNode(-1);
		tree.addNode(3);
		tree.addNode(7);
		tree.addNode(6);
		tree.addNode(8);
		tree.addNode(25);
		tree.addNode(19);
		tree.addNode(12);
		tree.addNode(21);
		tree.addNode(29);
		tree.addNode(27);
		tree.addNode(34);
		// Print tree element
		tree.printInorder(tree.root);
		// Test Cases
		tree.kthSmallestNode(4);
		tree.kthSmallestNode(8);
		tree.kthSmallestNode(5);
		tree.kthSmallestNode(1);
		tree.kthSmallestNode(14);
	}
}

input

  -1  2  3  4  6  7  8  10  12  19  21  25  27  29  34
 (4)-th smallest is : 4
 (8)-th smallest is : 10
 (5)-th smallest is : 6
 (1)-th smallest is : -1
 (14)-th smallest is : 29
// Swift 4 program
// Kth smallest element in a perfect binary search tree
class TreeNode
{
	// Data value
	var data: Int;
	// Indicates left and right subtree
	var left: TreeNode? ;
	var right: TreeNode? ;
	init(_ data: Int)
	{
		self.data = data;
		self.left = nil;
		self.right = nil;
	}
}
class BinarySearchTree
{
	var root: TreeNode? ;
	init()
	{
		self.root = nil;
	}
	// Print the inorder of binary tree nodes
	func printInorder(_ node: TreeNode? )
	{
		if (node  != nil)
		{
			self.printInorder(node!.left);
			//print node value
			print("  ", node!.data, terminator: "");
			self.printInorder(node!.right);
		}
	}
	// insert a node in BST
	func addNode(_ data: Int)
	{
		// Create new node of tree
		let node = TreeNode(data);
		if (self.root == nil)
		{
			self.root = node;
		}
		else
		{
			var auxiliary = self.root;
			// Add new node in binary search tree
			while (auxiliary  != nil)
			{
				if (data > auxiliary!.data)
				{
					if (auxiliary!.right == nil)
					{
						// Add new node at right child
						auxiliary!.right = node;
						return;
					}
					auxiliary = auxiliary!.right;
				}
				else
				{
					if (auxiliary!.left == nil)
					{
						// Add new node at left child
						auxiliary!.left = node;
						return;
					}
					auxiliary = auxiliary!.left;
				}
			}
		}
	}
	// Count number of nodes in binary tree
	func countNode(_ node: TreeNode? ) -> Int
	{
		if (node == nil)
		{
			return 0;
		}
		return self.countNode(node!.left) + self.countNode(node!.right) + 1;
	}
	func findKthSmallestNode(_ node: TreeNode? , _ k : Int, _ n: Int) -> TreeNode?
	{
		if (node == nil)
		{
			return nil;
		}
		let mid = (n / 2) + 1;
		if (mid == k)
		{
			// Get resultant node
			return node;
		}
		if (k < mid)
		{
			return self.findKthSmallestNode(node!.left, k, mid - 1);
		}
		else
		{
			return self.findKthSmallestNode(node!.right, k - mid, mid - 1);
		}
	}
	func kthSmallestNode(_ k: Int)
	{
		if (self.root == nil)
		{
			// When empty tree
			return;
		}
		// Count number of nodes in binary tree
		let n = self.countNode(self.root);
		if (k <= 0 || n < k)
		{
			// Invalid k
			return;
		}
		// Find kth smallest
		let result = self.findKthSmallestNode(self.root, k, n);
		// Display calculated result
		print("\n (", k ,")-th smallest is : ", result!.data, terminator: "");
	}
}
func main()
{
	let tree = BinarySearchTree();
	/*
	              10 
	             /  \
	            /    \
	           /      \ 
	          /        \
	         /          \                           
	        /            \    
	       4               25    
	      /  \            /  \   
	     /    \          /    \      
	    2       7       19     29
	   / \     / \     / \     / \ 
	  /   \   /   \   /   \   /   \
	 -1    3 6     8 12   21 27   34 
	-----------------
	  Constructing binary search tree
	*/
	tree.addNode(10);
	tree.addNode(4);
	tree.addNode(2);
	tree.addNode(-1);
	tree.addNode(3);
	tree.addNode(7);
	tree.addNode(6);
	tree.addNode(8);
	tree.addNode(25);
	tree.addNode(19);
	tree.addNode(12);
	tree.addNode(21);
	tree.addNode(29);
	tree.addNode(27);
	tree.addNode(34);
	// Print tree element
	tree.printInorder(tree.root);
	// Test Cases
	tree.kthSmallestNode(4);
	tree.kthSmallestNode(8);
	tree.kthSmallestNode(5);
	tree.kthSmallestNode(1);
	tree.kthSmallestNode(14);
}
main();

input

   -1   2   3   4   6   7   8   10   12   19   21   25   27   29   34
 ( 4 )-th smallest is :  4
 ( 8 )-th smallest is :  10
 ( 5 )-th smallest is :  6
 ( 1 )-th smallest is :  -1
 ( 14 )-th smallest is :  29
// Kotlin program
// Kth smallest element in a perfect binary search tree
class TreeNode
{
	// Data value
	var data: Int;
	// Indicates left and right subtree
	var left: TreeNode ? ;
	var right: TreeNode ? ;
	constructor(data: Int)
	{
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
class BinarySearchTree
{
	var root: TreeNode ? ;
	constructor()
	{
		this.root = null;
	}
	// Print the inorder of binary tree nodes
	fun printInorder(node: TreeNode ? ): Unit
	{
		if (node != null)
		{
			this.printInorder(node.left);
			//print node value
			print("  " + node.data);
			this.printInorder(node.right);
		}
	}
	// insert a node in BST
	fun addNode(data: Int): Unit
	{
		// Create new node of tree
		val node: TreeNode = TreeNode(data);
		if (this.root == null)
		{
			this.root = node;
		}
		else
		{
			var auxiliary: TreeNode ? = this.root;
			// Add new node in binary search tree
			while (auxiliary != null)
			{
				if (data > auxiliary.data)
				{
					if (auxiliary.right == null)
					{
						// Add new node at right child
						auxiliary.right = node;
						return;
					}
					auxiliary = auxiliary.right;
				}
				else
				{
					if (auxiliary.left == null)
					{
						// Add new node at left child
						auxiliary.left = node;
						return;
					}
					auxiliary = auxiliary.left;
				}
			}
		}
	}
	// Count number of nodes in binary tree
	fun countNode(node: TreeNode ? ): Int
	{
		if (node == null)
		{
			return 0;
		}
		return this.countNode(node.left) + this.countNode(node.right) + 1;
	}
	fun findKthSmallestNode(node: TreeNode ? , k : Int, n: Int): TreeNode ?
	{
		if (node == null)
		{
			return null;
		}
		val mid: Int = (n / 2) + 1;
		if (mid == k)
		{
			// Get resultant node
			return node;
		}
		if (k < mid)
		{
			return this.findKthSmallestNode(node.left, k, mid - 1);
		}
		else
		{
			return this.findKthSmallestNode(node.right, k - mid, mid - 1);
		}
	}
	fun kthSmallestNode(k: Int): Unit
	{
		if (this.root == null)
		{
			// When empty tree
			return;
		}
		// Count number of nodes in binary tree
		val n: Int = this.countNode(this.root);
		if (k <= 0 || n < k)
		{
			// Invalid k
			return;
		}
		// Find kth smallest
		val result: TreeNode? = this.findKthSmallestNode(this.root, k, n);
		// Display calculated result
		print("\n (" + k + ")-th smallest is : " + result!!.data);
	}
}
fun main(args: Array < String > ): Unit
{
	val tree: BinarySearchTree = BinarySearchTree();
	/*
	              10 
	             /  \
	            /    \
	           /      \ 
	          /        \
	         /          \                           
	        /            \    
	       4               25    
	      /  \            /  \   
	     /    \          /    \      
	    2       7       19     29
	   / \     / \     / \     / \ 
	  /   \   /   \   /   \   /   \
	 -1    3 6     8 12   21 27   34 
	-----------------
	  Constructing binary search tree
	*/
	tree.addNode(10);
	tree.addNode(4);
	tree.addNode(2);
	tree.addNode(-1);
	tree.addNode(3);
	tree.addNode(7);
	tree.addNode(6);
	tree.addNode(8);
	tree.addNode(25);
	tree.addNode(19);
	tree.addNode(12);
	tree.addNode(21);
	tree.addNode(29);
	tree.addNode(27);
	tree.addNode(34);
	// Print tree element
	tree.printInorder(tree.root);
	// Test Cases
	tree.kthSmallestNode(4);
	tree.kthSmallestNode(8);
	tree.kthSmallestNode(5);
	tree.kthSmallestNode(1);
	tree.kthSmallestNode(14);
}

input

  -1  2  3  4  6  7  8  10  12  19  21  25  27  29  34
 (4)-th smallest is : 4
 (8)-th smallest is : 10
 (5)-th smallest is : 6
 (1)-th smallest is : -1
 (14)-th smallest is : 29


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







© 2021, kalkicode.com, All rights reserved