Posted on by Kalkicode
Code Binary Search Tree

# 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
*/
// 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
{
// 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
*/
// 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 <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
{
// 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
*/
// 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
{
// 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
*/
// 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
{
// 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
*/
// 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
{
// 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
*/
// 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
#  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
#  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_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_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
#  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
#  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
*/
// 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
{
// 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
*/
// 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
{
// 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
*/
// 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

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

Categories
Relative Post