Binary Search Trees: Construct BST from preorder traversal
Problem Statement: You are given an array representing a preorder traversal of a Binary Search Tree and construct the BST. Solution WKT the first element in a pre-order traversal is always the root. So we take the first element as root, then we search for the element that is greater than the root. Then the […]
Binary Search Trees: LCA in a BST
Problem Statement: You are given a BST root node and 2 node values n1 and n2, you need to find the Lowest Common Ancestor. Solution As we know the property of BST, check if the current node is less than both n1 and n2 then LCA lies in the right subtree. Then call the recursive […]
Binary Search Trees: Convert a BST into greater sum tree
Problem Statement: You are given a root node of BST. You need to convert into a greater sum tree. Example Input: 4 / \ 3 6 Output: 6 / \ 10 0 Solution Greater sum tree is a tree in which every node contains the sum of all the nodes which are greater than the […]
Binary Search Trees: A program to check if a binary tree is BST or not
Problem Statement: You are given a root node of a binary tree. You need to find out if a binary tree is a BST or not. Solution BST will have below 2 properties: The left subtree of a node contains only node with data less than the node’s data The right subtree of a node […]
Binary Search Trees: Find the Inorder predecessor and successor for a given key in BST
Problem Statement: You are given BST root and a key, find the inorder predecessor and successor for that key. If the key is not found, then you need to return the 2 values in which the key lies. Solution If the root is NULL then return. If the key is found then if the left […]
Binary Search Trees: Find min and max value in a BST
Problem Statement: You are given a BST root node, you need to find the max and min value. Solution To get the min value, traverse the node from root to left recursively until left node is NULL. To get the max value, traverse the node from root to right recursively until right node is NULL. […]
Binary Search Trees: Deletion of a node in a BST
Problem Statement: You are given BST root node and a key value. You need to delete that node from BST. Solution There are few cases to be considered. 1. If the key is equal to the leaf node, then we can delete directly. 2. If the node is having children, then we need to choose […]
Binary Search Trees: Find a value in a BST
Problem Statement: Given a BST and a key element, you need to find if the key element is present in BST or not. Solution The solution is very simple. We take the key element and compare with the root, if the key element is smaller then we go to the left sub tree else we […]
Binary Trees: Find Duplicate Subtrees
Problem Statement: You are given a binary tree, you need to get all the duplicate subtree. You need to return the root of the sub trees. Example Output: The duplicate sub tree are: 2 / and 4 4 Here you need to return “2” and “4” Solution In the solution we will use map to […]
Binary Trees: Kth Ancestor of a Tree Node
Problem Statement: You are given a binary tree, a node and an integer “k”. You need to return the kth ancestor of that node. Example The 2nd ancestor of node 4 is node 1. Solution We will use DFS in this approach. We will find the given node in the tree. Then we backtrack to […]