In this post, we will implement Treap Data Structure and perform basic operations like insert, search and delete on it.
Write an efficient algorithm to find preorder traversal of a binary tree from its inorder and postorder sequence without constructing the tree.
Given a binary search tree, modify it such that every key is updated to contain sum of all greater keys present in BST.
Given a binary tree that is only one swap away from becoming a BST, convert the binary tree into BST in single traversal of it.
Given a binary tree, write an efficient algorithm to find maximum sum path between any two leaves in it.
Given a binary tree, write an efficient algorithm to find all nodes present at given distance from any leaf node. We need to find only those nodes that are present in root-to-leaf path for that leaf.
Given a binary tree, count all subtrees in it such that every node in the subtree have same value.
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.
Given a binary tree, find maximum difference between a node and its descendants in it.
Given a binary tree, write an efficient algorithm to print right view of given binary tree.
Given a binary tree whose nodes are labelled from 0 to n-1, construct an ancestor matrix from it. An ancestor matrix is a boolean matrix, whose cell (i, j) is true if i is ancestor of j in the binary tree.
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.