Build a Binary Search Tree from a preorder sequence
Given a distinct sequence of keys representing the preorder sequence of a binary search tree (BST), construct a BST from it.
Category: BST
Implementation of Treap Data Structure (Insert, Search, and Delete)
This post will implement a treap data structure, a combination of a binary search tree and a heap, and perform basic operations like insert, search, and delete on it.
Find inorder successor for the given key in a BST
Given a BST, find the inorder successor of a given key in it. If the given key does not lie in the BST, then return the next greater key (if any) present in the BST.
Fix a binary tree that is only one swap away from becoming a BST
Given a binary tree that is only one swap away from becoming a BST, convert it into a BST in a single traversal.
Update every key in a BST to contain the sum of all greater keys
Given a binary search tree, modify it such that every key is updated to contain the sum of all greater keys present in the BST.
Construct a height-balanced BST from a sorted doubly linked list
Given a sorted doubly linked list, in-place convert it into a height-balanced Binary Search Tree (BST). The difference between the height of the left and right subtree for every node of a height-balanced BST is never greater than 1.
Remove nodes from a BST that have keys outside a valid range
Given a BST and a valid range of keys, remove nodes from BST that have keys outside the valid range.
Find a pair with the given sum in a BST
Given a binary search tree, find a pair with a given sum present in it.
Find k’th smallest node in a BST
Given a BST and a positive number k, find the k’th smallest node in it.
Convert a binary tree to BST by maintaining its original structure
Convert a given binary tree into a BST (Binary Search Tree) by keeping its original structure intact.
Replace every array element with the least greater element on its right
Write an efficient algorithm to replace every element of a given array with the least greater element on its right or with -1 if there are no greater elements.
Treap Data Structure
A Treap data structure is basically a combination of a binary search tree and a heap.