Skip to main content

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




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.

New Comment