Ceil value in binary search tree
Here given code implementation process.
/*
C program for
Ceil 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;
}
// 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);
}
}
// 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;
}
}
}
}
}
int ceilValue(struct TreeNode *node, int key)
{
if (node == NULL)
{
return INT_MIN;
}
if (node->data == key)
{
// When given key is equal to node data
return node->data;
}
if (node->data < key)
{
// Visit right subtree
return ceilValue(node->right, key);
}
// Find ceil in left subtree
int x = ceilValue(node->left, key);
if (x >= key)
{
return x;
}
return node->data;
}
void ceilOfKey(struct TreeNode *root, int key)
{
if (root == NULL)
{
return;
}
// Display the ceil of given key
printf("\n Ceil of %d is : %d", key, ceilValue(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
ceilOfKey(tree->root, 6);
ceilOfKey(tree->root, 25);
ceilOfKey(tree->root, 17);
ceilOfKey(tree->root, 2);
ceilOfKey(tree->root, -5);
return 0;
}
Output
Tree Element : 9 3 1 -3 4 7 17 32 19
Ceil of 6 is : 7
Ceil of 25 is : 32
Ceil of 17 is : 17
Ceil of 2 is : 3
Ceil of -5 is : -3
/*
Java Program for
Ceil 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 ceilValue(TreeNode node, int key)
{
if (node == null)
{
return Integer.MIN_VALUE;
}
if (node.data == key)
{
// When given key is equal to node data
return node.data;
}
if (node.data < key)
{
// Visit right subtree
return ceilValue(node.right, key);
}
// Find ceil in left subtree
int x = ceilValue(node.left, key);
if (x >= key)
{
return x;
}
return node.data;
}
public void ceilOfKey(int key)
{
if (this.root == null)
{
return;
}
// Display the ceil of given key
System.out.print("\n Ceil of " + key + " is : " +
ceilValue(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.ceilOfKey(6);
tree.ceilOfKey(25);
tree.ceilOfKey(17);
tree.ceilOfKey(2);
tree.ceilOfKey(-5);
}
}
Output
Tree Element : 9 3 1 -3 4 7 17 32 19
Ceil of 6 is : 7
Ceil of 25 is : 32
Ceil of 17 is : 17
Ceil of 2 is : 3
Ceil of -5 is : -3
// Include header file
#include <iostream>
#include <limits.h>
using namespace std;
/*
C++ Program for
Ceil 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 ceilValue(TreeNode *node, int key)
{
if (node == NULL)
{
return INT_MIN;
}
if (node->data == key)
{
// When given key is equal to node data
return node->data;
}
if (node->data < key)
{
// Visit right subtree
return this->ceilValue(node->right, key);
}
// Find ceil in left subtree
int x = this->ceilValue(node->left, key);
if (x >= key)
{
return x;
}
return node->data;
}
void ceilOfKey(int key)
{
if (this->root == NULL)
{
return;
}
// Display the ceil of given key
cout << "\n Ceil of " << key << " is : "
<< this->ceilValue(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->ceilOfKey(6);
tree->ceilOfKey(25);
tree->ceilOfKey(17);
tree->ceilOfKey(2);
tree->ceilOfKey(-5);
return 0;
}
Output
Tree Element : 9 3 1 -3 4 7 17 32 19
Ceil of 6 is : 7
Ceil of 25 is : 32
Ceil of 17 is : 17
Ceil of 2 is : 3
Ceil of -5 is : -3
// Include namespace system
using System;
/*
Csharp Program for
Ceil 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 ceilValue(TreeNode node, int key)
{
if (node == null)
{
return int.MinValue;
}
if (node.data == key)
{
// When given key is equal to node data
return node.data;
}
if (node.data < key)
{
// Visit right subtree
return this.ceilValue(node.right, key);
}
// Find ceil in left subtree
int x = this.ceilValue(node.left, key);
if (x >= key)
{
return x;
}
return node.data;
}
public void ceilOfKey(int key)
{
if (this.root == null)
{
return;
}
// Display the ceil of given key
Console.Write("\n Ceil of " + key + " is : " +
this.ceilValue(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.ceilOfKey(6);
tree.ceilOfKey(25);
tree.ceilOfKey(17);
tree.ceilOfKey(2);
tree.ceilOfKey(-5);
}
}
Output
Tree Element : 9 3 1 -3 4 7 17 32 19
Ceil of 6 is : 7
Ceil of 25 is : 32
Ceil of 17 is : 17
Ceil of 2 is : 3
Ceil of -5 is : -3
package main
import "math"
import "fmt"
/*
Go Program for
Ceil 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) ceilValue(node * TreeNode, key int) int {
if node == nil {
return math.MinInt64
}
if node.data == key {
// When given key is equal to node data
return node.data
}
if node.data < key {
// Visit right subtree
return this.ceilValue(node.right, key)
}
// Find ceil in left subtree
var x int = this.ceilValue(node.left, key)
if x >= key {
return x
}
return node.data
}
func(this BinarySearchTree) ceilOfKey(key int) {
if this.root == nil {
return
}
// Display the ceil of given key
fmt.Print("\n Ceil of ", key, " is : ", this.ceilValue(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.ceilOfKey(6)
tree.ceilOfKey(25)
tree.ceilOfKey(17)
tree.ceilOfKey(2)
tree.ceilOfKey(-5)
}
Output
Tree Element : 9 3 1 -3 4 7 17 32 19
Ceil of 6 is : 7
Ceil of 25 is : 32
Ceil of 17 is : 17
Ceil of 2 is : 3
Ceil of -5 is : -3
<?php
/*
Php Program for
Ceil 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 ceilValue($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 right subtree
return $this->ceilValue($node->right, $key);
}
// Find ceil in left subtree
$x = $this->ceilValue($node->left, $key);
if ($x >= $key)
{
return $x;
}
return $node->data;
}
public function ceilOfKey($key)
{
if ($this->root == NULL)
{
return;
}
// Display the ceil of given key
echo("\n Ceil of ".$key.
" is : ".$this->ceilValue($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->ceilOfKey(6);
$tree->ceilOfKey(25);
$tree->ceilOfKey(17);
$tree->ceilOfKey(2);
$tree->ceilOfKey(-5);
}
main();
Output
Tree Element : 9 3 1 -3 4 7 17 32 19
Ceil of 6 is : 7
Ceil of 25 is : 32
Ceil of 17 is : 17
Ceil of 2 is : 3
Ceil of -5 is : -3
/*
Node JS Program for
Ceil 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);
}
}
ceilValue(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 right subtree
return this.ceilValue(node.right, key);
}
// Find ceil in left subtree
var x = this.ceilValue(node.left, key);
if (x >= key)
{
return x;
}
return node.data;
}
ceilOfKey(key)
{
if (this.root == null)
{
return;
}
// Display the ceil of given key
process.stdout.write("\n Ceil of " + key + " is : " +
this.ceilValue(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.ceilOfKey(6);
tree.ceilOfKey(25);
tree.ceilOfKey(17);
tree.ceilOfKey(2);
tree.ceilOfKey(-5);
}
main();
Output
Tree Element : 9 3 1 -3 4 7 17 32 19
Ceil of 6 is : 7
Ceil of 25 is : 32
Ceil of 17 is : 17
Ceil of 2 is : 3
Ceil of -5 is : -3
import sys
# Python 3 Program for
# Ceil 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 ceilValue(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 right subtree
return self.ceilValue(node.right, key)
# Find ceil in left subtree
x = self.ceilValue(node.left, key)
if (x >= key) :
return x
return node.data
def ceilOfKey(self, key) :
if (self.root == None) :
return
# Display the ceil of given key
print("\n Ceil of", key ,"is :",
self.ceilValue(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.ceilOfKey(6)
tree.ceilOfKey(25)
tree.ceilOfKey(17)
tree.ceilOfKey(2)
tree.ceilOfKey(-5)
if __name__ == "__main__": main()
Output
Tree Element : 9 3 1 -3 4 7 17 32 19
Ceil of 6 is : 7
Ceil of 25 is : 32
Ceil of 17 is : 17
Ceil of 2 is : 3
Ceil of -5 is : -3
# Ruby Program for
# Ceil 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 ceilValue(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 right subtree
return self.ceilValue(node.right, key)
end
# Find ceil in left subtree
x = self.ceilValue(node.left, key)
if (x >= key)
return x
end
return node.data
end
def ceilOfKey(key)
if (self.root == nil)
return
end
# Display the ceil of given key
print("\n Ceil of ", key ," is : ",
self.ceilValue(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.ceilOfKey(6)
tree.ceilOfKey(25)
tree.ceilOfKey(17)
tree.ceilOfKey(2)
tree.ceilOfKey(-5)
end
main()
Output
Tree Element : 9 3 1 -3 4 7 17 32 19
Ceil of 6 is : 7
Ceil of 25 is : 32
Ceil of 17 is : 17
Ceil of 2 is : 3
Ceil of -5 is : -3
/*
Scala Program for
Ceil 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 ceilValue(node: TreeNode, key: Int): Int = {
if (node == null)
{
return Int.MinValue;
}
if (node.data == key)
{
// When given key is equal to node data
return node.data;
}
if (node.data < key)
{
// Visit right subtree
return ceilValue(node.right, key);
}
// Find ceil in left subtree
var x: Int = ceilValue(node.left, key);
if (x >= key)
{
return x;
}
return node.data;
}
def ceilOfKey(key: Int): Unit = {
if (this.root == null)
{
return;
}
// Display the ceil of given key
print("\n Ceil of " + key + " is : " +
ceilValue(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.ceilOfKey(6);
tree.ceilOfKey(25);
tree.ceilOfKey(17);
tree.ceilOfKey(2);
tree.ceilOfKey(-5);
}
}
Output
Tree Element : 9 3 1 -3 4 7 17 32 19
Ceil of 6 is : 7
Ceil of 25 is : 32
Ceil of 17 is : 17
Ceil of 2 is : 3
Ceil of -5 is : -3
/*
Swift 4 Program for
Ceil 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 ceilValue(_ node: TreeNode? , _ key : Int) -> Int
{
if (node == nil)
{
return Int.min;
}
if (node!.data == key)
{
// When given key is equal to node data
return node!.data;
}
if (node!.data < key)
{
// Visit right subtree
return self.ceilValue(node!.right, key);
}
// Find ceil in left subtree
let x: Int = self.ceilValue(node!.left, key);
if (x >= key)
{
return x;
}
return node!.data;
}
func ceilOfKey(_ key: Int)
{
if (self.root == nil)
{
return;
}
// Display the ceil of given key
print("\n Ceil of", key ,"is :",
self.ceilValue(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.ceilOfKey(6);
tree.ceilOfKey(25);
tree.ceilOfKey(17);
tree.ceilOfKey(2);
tree.ceilOfKey(-5);
}
main();
Output
Tree Element : 9 3 1 -3 4 7 17 32 19
Ceil of 6 is : 7
Ceil of 25 is : 32
Ceil of 17 is : 17
Ceil of 2 is : 3
Ceil of -5 is : -3
/*
Kotlin Program for
Ceil 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 ceilValue(node: TreeNode ? , key : Int): Int
{
if (node == null)
{
return Int.MIN_VALUE;
}
if (node.data == key)
{
// When given key is equal to node data
return node.data;
}
if (node.data < key)
{
// Visit right subtree
return this.ceilValue(node.right, key);
}
// Find ceil in left subtree
val x: Int = this.ceilValue(node.left, key);
if (x >= key)
{
return x;
}
return node.data;
}
fun ceilOfKey(key: Int): Unit
{
if (this.root == null)
{
return;
}
// Display the ceil of given key
print("\n Ceil of " + key + " is : " + this.ceilValue(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.ceilOfKey(6);
tree.ceilOfKey(25);
tree.ceilOfKey(17);
tree.ceilOfKey(2);
tree.ceilOfKey(-5);
}
Output
Tree Element : 9 3 1 -3 4 7 17 32 19
Ceil of 6 is : 7
Ceil of 25 is : 32
Ceil of 17 is : 17
Ceil of 2 is : 3
Ceil of -5 is : -3
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