Treap Data Structure
A Treap data structure is basically a combination of a binary search tree and a heap.
Category: Tree
Print binary tree structure with its contents
Write an efficient algorithm to print a binary tree structure in standard output.
Find Floor and Ceil in a Binary Search Tree
Given a BST, find the floor and ceil of a given key in it. If the given key lies in the BST, then both floor and ceil are equal to that key; otherwise, the ceil is equal to the next greater key (if any) in the BST, and the floor is equal to the previous greater key (if any) in the BST.
Find k’th largest node in a BST
Given a BST and a positive number k, find the k’th largest node in the BST.
Find the Lowest Common Ancestor (LCA) of two nodes in a BST
Given a BST and two nodes x and y in it, find the lowest common ancestor (LCA) of x and y. The LCA of x and y is the shared ancestor of x and y that is located farthest from the root.
Find inorder predecessor for the given key in a BST
Given a BST, find the inorder predecessor of a given key in it. If the key does not lie in the BST, return the previous greater key (if any) present in the BST.
Check if the given keys represent the same BSTs or not without building BST
Given two arrays that represent a set of BST keys, check if they represent the same BSTs or not. We are not allowed to build the tree.
Find the diagonal sum of a binary tree
Given a binary tree, calculate the sum of all nodes for each diagonal having negative slope (\). Assume that the left and right child of a node makes a 45–degree angle with the parent.
Determine whether a 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 is the key to figuring out whether a tree is a BST or not.
Construct a balanced BST from the given keys
Given an unsorted integer array that represents binary search tree keys, construct a height-balanced BST from it.
Deletion from BST (Binary Search Tree)
Deletion from BST – write an efficient function to delete a given key in BST. To delete a node from BST, there are three possible cases to consider.
Search a given key in BST – Iterative and Recursive Solution
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 the 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.