Category: BST

Binary Search Trees

Floor and Ceil in a Binary Search Tree

Given a BST, find ceil and floor of a given key in it. If the given key lie in the BST, then both floor and ceil is equal to that key, else ceil is equal to next greater key (if any) in the BST and floor is equal to previous greater key (if any) in …

Find inorder predecessor for given key in a BST

Given a BST, find in-order predecessor of a given key in it. If the given key do not lie in the BST, then return the previous greater key (if any) present in the BST.   An in-order predecessor of a node in BST is the previous node in in-order traversal of it.

Determine if given Binary Tree is a BST or not

Given a Binary Tree, determine if it is a BST or not.   This problem has a simple recursive solution. The BST property “every node on the right subtree has to be larger than the current node and every node on the left subtree has to be smaller than the current node” is the key …

Deletion from BST

Given a BST, write an efficient function to delete a given key in it.  

Search given key in BST

Given a BST, write an efficient function to search a given key in it. The algorithm should return the parent node of the key and print if the key is left or right node of the parent node. If the key is not present in the BST, the algorithm should be able to determine that.

Insertion in BST

  A Binary Search Tree (BST) is a rooted binary tree, whose nodes each store a key (and optionally, an associated value) and each have two distinguished sub-trees, commonly denoted left and right. The tree should satisfy the BST property, which states that the key in each node must be greater than all keys stored …

Find optimal cost to construct Binary Search Tree

Find optimal cost to construct binary search tree where each key can repeat several times. We are given frequency of each key in same order as corresponding keys in inorder traversal of a binary search tree.