Binary Search Trees: Find triplet sum in BST
Problem Statement: You are given a BST node and a key. YOu need to find if that key exist any triplet sum in given BST. Solution We do in-order traversal of the BST, we get the sorted order and store in an array. Then we have reduced the problem to check if triplet sum exist […]
Binary Search Trees: Convert sorted DLL to Balanced BST
Problem Statement: You are given an DLL where the nodes are sorted in ascending order. we need to construct Balanced BST in-place. In-place means, no new nodes should be allocated for tree conversion. Solution Below are the steps to be followed to arrive at the solution: 1. Get the middle of the LL and make […]
Binary Search Trees: Count the number of BST nodes that lie in a given range.
Solution The solution is very simple. For every node visited, check if the node lies in range, if yes, then increment the count. Then recursion for both of its children. If the current node is smaller than low value, then recursion the right child, else recursion the left child. Solution in C++ #include<iostream> #include<vector> #include<string> […]
Binary Search Trees: Get the Shortest distance between two nodes in BST
Problem Statement: You are given the root node of BST and 2 key elements. You need to find the distance between the 2 nodes. Solution So as the tree is a BST, if both the keys are greater than the current node, then move right else move to left child. Then if one key is […]
Binary Search Trees: Return the sum of given range in BST.
Problem Statement: You are given a root of BST and 2 values. You need to return the sum of the nodes that falls within the range. Solution For solution we follow below steps: 1. We take a node, and check if the node value is less than left, then we move to right. 2. We […]
Binary Search Trees: Kth smallest Element in a BST
Problem Statement: You are given BST and a kth element in the given tree. Then you need to give the kth smallest element. Solution Solution is very simple. We will take in-order traversal and store it an array. Then we take the kth smallest element. Solution in C++ #include<iostream> #include<vector> #include<string> #include<set> using namespace std; […]
Binary Search Trees: Kth Largest Element in a BST
Problem Statement: You are given BST and a kth element in the given tree. Then you need to give the kth largest element. Solution Here we need to do reverse inorder traversal of BST and we need to keep a count of nodes visited. It means, in reverse in-order traversal visit the right node then […]
Binary Search Trees: Merge Two balanced BST
Problem Statement: You are given two balanced BST, you need to merge the two given balanced BST. Solution THe solution is very simple. WKT in-order traversal of BST will give the sorted order. So we need to perform in-order traversal of both BST, we will get two sorted arrays. Then we need to merge two […]
Binary Search Trees: Convert a normal BST into a Balanced BST
Problem Statement: You are given a BST root node, you need to make it as a balanced BST. Example Input: 3 / 2 / 1 Output: 2 / \ 1 3 Solution The solution is simple. We follow below steps: 1. Get the nodes of BST in in-order traversal and store the result int he […]
Binary Search Trees: Convert Binary Tree into Binary Search Tree.
Example Input: 11 / \ 3 8 / \ 9 5 Output: 9 / \ 5 11 / \ 3 8 Solution The solution is simple: 1. Take the node values into an temp array by doing inorder traversal of the tree. 2. Then sort the array 3. Then do an inorder traversal of the […]