Category: Binary Search Tree (BST)

Update every key in BST to contain sum of all greater keys

Given a binary search tree, modify it such that every key is updated to contain sum of all greater keys present in BST.

Find Inorder Successor for given key in a BST

Given a BST, find inorder successor of a given key in it. If the given key do not lie in the BST, then return the next greater key (if any) 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 BST that have keys outside the 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 given sum in a BST

Given a binary search tree, find a pair with given sum present in it.

Convert a Binary Tree to BST by maintaining its original structure

Convert a given binary tree to BST (Binary Search Tree) by keeping original structure of the binary tree intact.

Replace every element of an array 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 element.

Print Binary Tree Structure with its contents in C++

Given a binary tree, write an efficient algorithm to print binary tree structure in standard output.

Floor and Ceil in a Binary Search Tree

Given a BST, find floor and ceil 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 K’th smallest and K’th largest element in BST

Given a Binary Search Tree and a positive number K, find K’th smallest and K’th largest element in BST.

Find Lowest Common Ancestor (LCA) of two nodes in a BST

Given a BST and two nodes x and y in it, find lowest common ancestor (LCA) of x and y in it.

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.