Floor value in binary search tree
Here given code implementation process.
/*
C program for
Floor value in binary search tree
*/
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
// Tree Node
struct TreeNode
{
int data;
struct TreeNode *left;
struct TreeNode *right;
};
// Binary Search Tree
struct BinarySearchTree
{
struct TreeNode *root;
};
// Create new tree
struct BinarySearchTree *newTree()
{
// Create dynamic node
struct BinarySearchTree *tree = (struct BinarySearchTree *)
malloc(sizeof(struct BinarySearchTree));
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 search 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 BinarySearchTree *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;
}
}
}
}
}
// Recursive function
// Display preorder view of binary search tree
void preorder(struct TreeNode *node)
{
if (node != NULL)
{
// Print node value
printf(" %d", node->data);
preorder(node->left);
preorder(node->right);
}
}
int floorValue(struct TreeNode *node, int key)
{
if (node == NULL)
{
return INT_MAX;
}
if (node->data == key)
{
// When given key is equal to node data
return node->data;
}
if (node->data > key)
{
// Visit left subtree
return floorValue(node->left, key);
}
// Find floor in right subtree
int x = floorValue(node->right, key);
if (x <= key)
{
return x;
}
return node->data;
}
void floorOfKey(struct TreeNode *root, int key)
{
if (root == NULL)
{
return;
}
// Display the floor of given key
printf("\n floor of %d is : %d", key, floorValue(root, key));
}
int main()
{
struct BinarySearchTree *tree = newTree();
/*
9
/ \
3 17
/ \ \
1 4 32
/ \ /
-3 7 19
-----------------
Binary Search Tree
*/
addNode(tree, 9);
addNode(tree, 3);
addNode(tree, 4);
addNode(tree, 7);
addNode(tree, 1);
addNode(tree, -3);
addNode(tree, 17);
addNode(tree, 32);
addNode(tree, 19);
printf("\n Tree Element : ");
preorder(tree->root);
// Test Inputs
floorOfKey(tree->root, 6);
floorOfKey(tree->root, 25);
floorOfKey(tree->root, 17);
floorOfKey(tree->root, 2);
floorOfKey(tree->root, 43);
return 0;
}
Output
Tree Element : 9 3 1 -3 4 7 17 32 19
floor of 6 is : 4
floor of 25 is : 19
floor of 17 is : 17
floor of 2 is : 1
floor of 43 is : 32
/*
Java Program for
Floor value in 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;
}
// 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;
}
}
}
}
// Recursive function
// Display preorder view of binary search tree
public void preorder(TreeNode node)
{
if (node != null)
{
// Print node value
System.out.print(" " + node.data);
preorder(node.left);
preorder(node.right);
}
}
public int floorValue(TreeNode node, int key)
{
if (node == null)
{
return Integer.MAX_VALUE;
}
if (node.data == key)
{
// When given key is equal to node data
return node.data;
}
if (node.data > key)
{
// Visit left subtree
return floorValue(node.left, key);
}
// Find floor in right subtree
int x = floorValue(node.right, key);
if (x <= key)
{
return x;
}
return node.data;
}
public void floorOfKey(int key)
{
if (this.root == null)
{
return;
}
// Display the floor of given key
System.out.print("\n floor of " + key + " is : " +
floorValue(this.root, key));
}
public static void main(String[] args)
{
BinarySearchTree tree = new BinarySearchTree();
/*
9
/ \
3 17
/ \ \
1 4 32
/ \ /
-3 7 19
-----------------
Binary Search Tree
*/
tree.addNode(9);
tree.addNode(3);
tree.addNode(4);
tree.addNode(7);
tree.addNode(1);
tree.addNode(-3);
tree.addNode(17);
tree.addNode(32);
tree.addNode(19);
System.out.print("\n Tree Element : ");
tree.preorder(tree.root);
// Test Inputs
tree.floorOfKey(6);
tree.floorOfKey(25);
tree.floorOfKey(17);
tree.floorOfKey(2);
tree.floorOfKey(43);
}
}
Output
Tree Element : 9 3 1 -3 4 7 17 32 19
floor of 6 is : 4
floor of 25 is : 19
floor of 17 is : 17
floor of 2 is : 1
floor of 43 is : 32
// Include header file
#include <iostream>
#include <limits.h>
using namespace std;
/*
C++ Program for
Floor value in 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;
}
// 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;
}
}
}
}
// Recursive function
// Display preorder view of binary search tree
void preorder(TreeNode *node)
{
if (node != NULL)
{
// Print node value
cout << " " << node->data;
this->preorder(node->left);
this->preorder(node->right);
}
}
int floorValue(TreeNode *node, int key)
{
if (node == NULL)
{
return INT_MAX;
}
if (node->data == key)
{
// When given key is equal to node data
return node->data;
}
if (node->data > key)
{
// Visit left subtree
return this->floorValue(node->left, key);
}
// Find floor in right subtree
int x = this->floorValue(node->right, key);
if (x <= key)
{
return x;
}
return node->data;
}
void floorOfKey(int key)
{
if (this->root == NULL)
{
return;
}
// Display the floor of given key
cout << "\n floor of " << key << " is : "
<< this->floorValue(this->root, key);
}
};
int main()
{
BinarySearchTree *tree = new BinarySearchTree();
/*
9
/ \
3 17
/ \ \
1 4 32
/ \ /
-3 7 19
-----------------
Binary Search Tree
*/
tree->addNode(9);
tree->addNode(3);
tree->addNode(4);
tree->addNode(7);
tree->addNode(1);
tree->addNode(-3);
tree->addNode(17);
tree->addNode(32);
tree->addNode(19);
cout << "\n Tree Element : ";
tree->preorder(tree->root);
// Test Inputs
tree->floorOfKey(6);
tree->floorOfKey(25);
tree->floorOfKey(17);
tree->floorOfKey(2);
tree->floorOfKey(43);
return 0;
}
Output
Tree Element : 9 3 1 -3 4 7 17 32 19
floor of 6 is : 4
floor of 25 is : 19
floor of 17 is : 17
floor of 2 is : 1
floor of 43 is : 32
// Include namespace system
using System;
/*
Csharp Program for
Floor value in 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;
}
// 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;
}
}
}
}
// Recursive function
// Display preorder view of binary search tree
public void preorder(TreeNode node)
{
if (node != null)
{
// Print node value
Console.Write(" " + node.data);
this.preorder(node.left);
this.preorder(node.right);
}
}
public int floorValue(TreeNode node, int key)
{
if (node == null)
{
return int.MaxValue;
}
if (node.data == key)
{
// When given key is equal to node data
return node.data;
}
if (node.data > key)
{
// Visit left subtree
return this.floorValue(node.left, key);
}
// Find floor in right subtree
int x = this.floorValue(node.right, key);
if (x <= key)
{
return x;
}
return node.data;
}
public void floorOfKey(int key)
{
if (this.root == null)
{
return;
}
// Display the floor of given key
Console.Write("\n floor of " + key + " is : " +
this.floorValue(this.root, key));
}
public static void Main(String[] args)
{
BinarySearchTree tree = new BinarySearchTree();
/*
9
/ \
3 17
/ \ \
1 4 32
/ \ /
-3 7 19
-----------------
Binary Search Tree
*/
tree.addNode(9);
tree.addNode(3);
tree.addNode(4);
tree.addNode(7);
tree.addNode(1);
tree.addNode(-3);
tree.addNode(17);
tree.addNode(32);
tree.addNode(19);
Console.Write("\n Tree Element : ");
tree.preorder(tree.root);
// Test Inputs
tree.floorOfKey(6);
tree.floorOfKey(25);
tree.floorOfKey(17);
tree.floorOfKey(2);
tree.floorOfKey(43);
}
}
Output
Tree Element : 9 3 1 -3 4 7 17 32 19
floor of 6 is : 4
floor of 25 is : 19
floor of 17 is : 17
floor of 2 is : 1
floor of 43 is : 32
package main
import "math"
import "fmt"
/*
Go Program for
Floor value in binary search tree
*/
type TreeNode struct {
// Data value
data int
// Indicates left and right subtree
left * TreeNode
right * TreeNode
}
func getTreeNode(data int) * TreeNode {
var me *TreeNode = &TreeNode {}
me.data = data
me.left = nil
me.right = nil
return me
}
type BinarySearchTree struct {
root * TreeNode
}
func getBinarySearchTree() * BinarySearchTree {
var me *BinarySearchTree = &BinarySearchTree {}
me.root = nil
return me
}
// insert a node in BST
func(this *BinarySearchTree) addNode(data int) {
// Create new node of tree
var node * TreeNode = getTreeNode(data)
if this.root == nil {
this.root = node
} else {
var auxiliary * TreeNode = this.root
// Add new node in binary search tree
for (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
}
}
}
}
// Recursive function
// Display preorder view of binary search tree
func(this BinarySearchTree) preorder(node * TreeNode) {
if node != nil {
// Print node value
fmt.Print(" ", node.data)
this.preorder(node.left)
this.preorder(node.right)
}
}
func(this BinarySearchTree) floorValue(node * TreeNode, key int) int {
if node == nil {
return math.MaxInt64
}
if node.data == key {
// When given key is equal to node data
return node.data
}
if node.data > key {
// Visit left subtree
return this.floorValue(node.left, key)
}
// Find floor in right subtree
var x int = this.floorValue(node.right, key)
if x <= key {
return x
}
return node.data
}
func(this BinarySearchTree) floorOfKey(key int) {
if this.root == nil {
return
}
// Display the floor of given key
fmt.Print("\n floor of ", key, " is : ",
this.floorValue(this.root, key))
}
func main() {
var tree * BinarySearchTree = getBinarySearchTree()
/*
9
/ \
3 17
/ \ \
1 4 32
/ \ /
-3 7 19
-----------------
Binary Search Tree
*/
tree.addNode(9)
tree.addNode(3)
tree.addNode(4)
tree.addNode(7)
tree.addNode(1)
tree.addNode(-3)
tree.addNode(17)
tree.addNode(32)
tree.addNode(19)
fmt.Print("\n Tree Element : ")
tree.preorder(tree.root)
// Test Inputs
tree.floorOfKey(6)
tree.floorOfKey(25)
tree.floorOfKey(17)
tree.floorOfKey(2)
tree.floorOfKey(43)
}
Output
Tree Element : 9 3 1 -3 4 7 17 32 19
floor of 6 is : 4
floor of 25 is : 19
floor of 17 is : 17
floor of 2 is : 1
floor of 43 is : 32
<?php
/*
Php Program for
Floor value in 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;
}
// 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;
}
}
}
}
// Recursive function
// Display preorder view of binary search tree
public function preorder($node)
{
if ($node != NULL)
{
// Print node value
echo(" ".$node->data);
$this->preorder($node->left);
$this->preorder($node->right);
}
}
public function floorValue($node, $key)
{
if ($node == NULL)
{
return PHP_INT_MAX;
}
if ($node->data == $key)
{
// When given key is equal to node data
return $node->data;
}
if ($node->data > $key)
{
// Visit left subtree
return $this->floorValue($node->left, $key);
}
// Find floor in right subtree
$x = $this->floorValue($node->right, $key);
if ($x <= $key)
{
return $x;
}
return $node->data;
}
public function floorOfKey($key)
{
if ($this->root == NULL)
{
return;
}
// Display the floor of given key
echo("\n floor of ".$key.
" is : ".$this->floorValue($this->root, $key));
}
}
function main()
{
$tree = new BinarySearchTree();
/*
9
/ \
3 17
/ \ \
1 4 32
/ \ /
-3 7 19
-----------------
Binary Search Tree
*/
$tree->addNode(9);
$tree->addNode(3);
$tree->addNode(4);
$tree->addNode(7);
$tree->addNode(1);
$tree->addNode(-3);
$tree->addNode(17);
$tree->addNode(32);
$tree->addNode(19);
echo("\n Tree Element : ");
$tree->preorder($tree->root);
// Test Inputs
$tree->floorOfKey(6);
$tree->floorOfKey(25);
$tree->floorOfKey(17);
$tree->floorOfKey(2);
$tree->floorOfKey(43);
}
main();
Output
Tree Element : 9 3 1 -3 4 7 17 32 19
floor of 6 is : 4
floor of 25 is : 19
floor of 17 is : 17
floor of 2 is : 1
floor of 43 is : 32
/*
Node JS Program for
Floor value in binary search tree
*/
class TreeNode
{
constructor(data)
{
this.data = data;
this.left = null;
this.right = null;
}
}
class BinarySearchTree
{
constructor()
{
this.root = null;
}
// 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;
}
}
}
}
// Recursive function
// Display preorder view of binary search tree
preorder(node)
{
if (node != null)
{
// Print node value
process.stdout.write(" " + node.data);
this.preorder(node.left);
this.preorder(node.right);
}
}
floorValue(node, key)
{
if (node == null)
{
return Number.MAX_VALUE;
}
if (node.data == key)
{
// When given key is equal to node data
return node.data;
}
if (node.data > key)
{
// Visit left subtree
return this.floorValue(node.left, key);
}
// Find floor in right subtree
var x = this.floorValue(node.right, key);
if (x <= key)
{
return x;
}
return node.data;
}
floorOfKey(key)
{
if (this.root == null)
{
return;
}
// Display the floor of given key
process.stdout.write("\n floor of " + key + " is : " +
this.floorValue(this.root, key));
}
}
function main()
{
var tree = new BinarySearchTree();
/*
9
/ \
3 17
/ \ \
1 4 32
/ \ /
-3 7 19
-----------------
Binary Search Tree
*/
tree.addNode(9);
tree.addNode(3);
tree.addNode(4);
tree.addNode(7);
tree.addNode(1);
tree.addNode(-3);
tree.addNode(17);
tree.addNode(32);
tree.addNode(19);
process.stdout.write("\n Tree Element : ");
tree.preorder(tree.root);
// Test Inputs
tree.floorOfKey(6);
tree.floorOfKey(25);
tree.floorOfKey(17);
tree.floorOfKey(2);
tree.floorOfKey(43);
}
main();
Output
Tree Element : 9 3 1 -3 4 7 17 32 19
floor of 6 is : 4
floor of 25 is : 19
floor of 17 is : 17
floor of 2 is : 1
floor of 43 is : 32
import sys
# Python 3 Program for
# Floor value in 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
# 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
# Recursive function
# Display preorder view of binary search tree
def preorder(self, node) :
if (node != None) :
# Print node value
print(" ", node.data, end = "")
self.preorder(node.left)
self.preorder(node.right)
def floorValue(self, node, key) :
if (node == None) :
return sys.maxsize
if (node.data == key) :
# When given key is equal to node data
return node.data
if (node.data > key) :
# Visit left subtree
return self.floorValue(node.left, key)
# Find floor in right subtree
x = self.floorValue(node.right, key)
if (x <= key) :
return x
return node.data
def floorOfKey(self, key) :
if (self.root == None) :
return
# Display the floor of given key
print("\n floor of ", key ," is : ",
self.floorValue(self.root, key), end = "")
def main() :
tree = BinarySearchTree()
# 9
# / \
# 3 17
# / \ \
# 1 4 32
# / \ /
# -3 7 19
# -----------------
# Binary Search Tree
tree.addNode(9)
tree.addNode(3)
tree.addNode(4)
tree.addNode(7)
tree.addNode(1)
tree.addNode(-3)
tree.addNode(17)
tree.addNode(32)
tree.addNode(19)
print("\n Tree Element : ", end = "")
tree.preorder(tree.root)
# Test Inputs
tree.floorOfKey(6)
tree.floorOfKey(25)
tree.floorOfKey(17)
tree.floorOfKey(2)
tree.floorOfKey(43)
if __name__ == "__main__": main()
Output
Tree Element : 9 3 1 -3 4 7 17 32 19
floor of 6 is : 4
floor of 25 is : 19
floor of 17 is : 17
floor of 2 is : 1
floor of 43 is : 32
# Ruby Program for
# Floor value in 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
# 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
# Recursive function
# Display preorder view of binary search tree
def preorder(node)
if (node != nil)
# Print node value
print(" ", node.data)
self.preorder(node.left)
self.preorder(node.right)
end
end
def floorValue(node, key)
if (node == nil)
return (2 ** (0. size * 8 - 2))
end
if (node.data == key)
# When given key is equal to node data
return node.data
end
if (node.data > key)
# Visit left subtree
return self.floorValue(node.left, key)
end
# Find floor in right subtree
x = self.floorValue(node.right, key)
if (x <= key)
return x
end
return node.data
end
def floorOfKey(key)
if (self.root == nil)
return
end
# Display the floor of given key
print("\n floor of ", key ," is : ",
self.floorValue(self.root, key))
end
end
def main()
tree = BinarySearchTree.new()
# 9
# / \
# 3 17
# / \ \
# 1 4 32
# / \ /
# -3 7 19
# -----------------
# Binary Search Tree
tree.addNode(9)
tree.addNode(3)
tree.addNode(4)
tree.addNode(7)
tree.addNode(1)
tree.addNode(-3)
tree.addNode(17)
tree.addNode(32)
tree.addNode(19)
print("\n Tree Element : ")
tree.preorder(tree.root)
# Test Inputs
tree.floorOfKey(6)
tree.floorOfKey(25)
tree.floorOfKey(17)
tree.floorOfKey(2)
tree.floorOfKey(43)
end
main()
Output
Tree Element : 9 3 1 -3 4 7 17 32 19
floor of 6 is : 4
floor of 25 is : 19
floor of 17 is : 17
floor of 2 is : 1
floor of 43 is : 32
/*
Scala Program for
Floor value in 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);
}
// 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;
}
}
}
}
// Recursive function
// Display preorder view of binary search tree
def preorder(node: TreeNode): Unit = {
if (node != null)
{
// Print node value
print(" " + node.data);
preorder(node.left);
preorder(node.right);
}
}
def floorValue(node: TreeNode, key: Int): Int = {
if (node == null)
{
return Int.MaxValue;
}
if (node.data == key)
{
// When given key is equal to node data
return node.data;
}
if (node.data > key)
{
// Visit left subtree
return floorValue(node.left, key);
}
// Find floor in right subtree
var x: Int = floorValue(node.right, key);
if (x <= key)
{
return x;
}
return node.data;
}
def floorOfKey(key: Int): Unit = {
if (this.root == null)
{
return;
}
// Display the floor of given key
print("\n floor of " + key + " is : " + floorValue(this.root, key));
}
}
object Main
{
def main(args: Array[String]): Unit = {
var tree: BinarySearchTree = new BinarySearchTree();
/*
9
/ \
3 17
/ \ \
1 4 32
/ \ /
-3 7 19
-----------------
Binary Search Tree
*/
tree.addNode(9);
tree.addNode(3);
tree.addNode(4);
tree.addNode(7);
tree.addNode(1);
tree.addNode(-3);
tree.addNode(17);
tree.addNode(32);
tree.addNode(19);
print("\n Tree Element : ");
tree.preorder(tree.root);
// Test Inputs
tree.floorOfKey(6);
tree.floorOfKey(25);
tree.floorOfKey(17);
tree.floorOfKey(2);
tree.floorOfKey(43);
}
}
Output
Tree Element : 9 3 1 -3 4 7 17 32 19
floor of 6 is : 4
floor of 25 is : 19
floor of 17 is : 17
floor of 2 is : 1
floor of 43 is : 32
/*
Swift 4 Program for
Floor value in 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;
}
// insert a node in BST
func addNode(_ data: Int)
{
// Create new node of tree
let node: TreeNode = TreeNode(data);
if (self.root == nil)
{
self.root = node;
}
else
{
var auxiliary: TreeNode? = 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;
}
}
}
}
// Recursive function
// Display preorder view of binary search tree
func preorder(_ node: TreeNode? )
{
if (node != nil)
{
// Print node value
print(" ", node!.data, terminator: "");
self.preorder(node!.left);
self.preorder(node!.right);
}
}
func floorValue(_ node: TreeNode? , _ key : Int) -> Int
{
if (node == nil)
{
return Int.max;
}
if (node!.data == key)
{
// When given key is equal to node data
return node!.data;
}
if (node!.data > key)
{
// Visit left subtree
return self.floorValue(node!.left, key);
}
// Find floor in right subtree
let x: Int = self.floorValue(node!.right, key);
if (x <= key)
{
return x;
}
return node!.data;
}
func floorOfKey(_ key: Int)
{
if (self.root == nil)
{
return;
}
// Display the floor of given key
print("\n floor of ", key ," is : ",
self.floorValue(self.root, key),
terminator: "");
}
}
func main()
{
let tree: BinarySearchTree = BinarySearchTree();
/*
9
/ \
3 17
/ \ \
1 4 32
/ \ /
-3 7 19
-----------------
Binary Search Tree
*/
tree.addNode(9);
tree.addNode(3);
tree.addNode(4);
tree.addNode(7);
tree.addNode(1);
tree.addNode(-3);
tree.addNode(17);
tree.addNode(32);
tree.addNode(19);
print("\n Tree Element : ", terminator: "");
tree.preorder(tree.root);
// Test Inputs
tree.floorOfKey(6);
tree.floorOfKey(25);
tree.floorOfKey(17);
tree.floorOfKey(2);
tree.floorOfKey(43);
}
main();
Output
Tree Element : 9 3 1 -3 4 7 17 32 19
floor of 6 is : 4
floor of 25 is : 19
floor of 17 is : 17
floor of 2 is : 1
floor of 43 is : 32
/*
Kotlin Program for
Floor value in 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;
}
// 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;
}
}
}
}
// Recursive function
// Display preorder view of binary search tree
fun preorder(node: TreeNode ? ): Unit
{
if (node != null)
{
// Print node value
print(" " + node.data);
this.preorder(node.left);
this.preorder(node.right);
}
}
fun floorValue(node: TreeNode ? , key : Int): Int
{
if (node == null)
{
return Int.MAX_VALUE;
}
if (node.data == key)
{
// When given key is equal to node data
return node.data;
}
if (node.data > key)
{
// Visit left subtree
return this.floorValue(node.left, key);
}
// Find floor in right subtree
val x: Int = this.floorValue(node.right, key);
if (x <= key)
{
return x;
}
return node.data;
}
fun floorOfKey(key: Int): Unit
{
if (this.root == null)
{
return;
}
// Display the floor of given key
print("\n floor of " + key + " is : " +
this.floorValue(this.root, key));
}
}
fun main(args: Array < String > ): Unit
{
val tree: BinarySearchTree = BinarySearchTree();
/*
9
/ \
3 17
/ \ \
1 4 32
/ \ /
-3 7 19
-----------------
Binary Search Tree
*/
tree.addNode(9);
tree.addNode(3);
tree.addNode(4);
tree.addNode(7);
tree.addNode(1);
tree.addNode(-3);
tree.addNode(17);
tree.addNode(32);
tree.addNode(19);
print("\n Tree Element : ");
tree.preorder(tree.root);
// Test Inputs
tree.floorOfKey(6);
tree.floorOfKey(25);
tree.floorOfKey(17);
tree.floorOfKey(2);
tree.floorOfKey(43);
}
Output
Tree Element : 9 3 1 -3 4 7 17 32 19
floor of 6 is : 4
floor of 25 is : 19
floor of 17 is : 17
floor of 2 is : 1
floor of 43 is : 32
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