Posts

Showing posts from November, 2022

Find Mode in a Binary Search Tree using C++

 Find Mode in a Binary Search Tree Given the root of a Binary Search Tree and we have to find the element which has the maximum frequency. There could be more than one element so we will store the elements in a vector. Approach: We will find the frequency of every element by using maps and also side by side, we will be finding the maximum frequency. Though the maximum frequency can be found later but it would take an extra traversal. For traversing, we can use any method, here I have used the inorder traversal. Finally, we will add every element having a frequency equal to the maximum frequency to the answer vector and return the vector.     Time Complexity:          For traversing the BST: O(n)          For Traversing the Map: O(n)     Space Complexity:          For storing elements: O(n)     C++ Code:      class Solution {      public:   ...

Predecessor and Successor of a Binary Search Tree using C++

 Predecessor and Successor of a Binary Search Tree Given the root of a binary search tree and a key. we have to find the in-order predecessor and successor of the given key. Approach: We know that the in-order traversal of a binary search tree is always sorted. So, the predecessor will be the value that is just smaller than the key and the successor will be the value that is just larger than the key. Successor: we will start traversing from the root. If the value of the root is less than or equal to the key, it means, the successor lies on right, so update the value of the root to root->right and if the value of the root is smaller than the key then the successor may be the root or it lies on the left side. So update the value of successor to root and the root to root->left and repeat the process unless root becomes NULL.     Time Complexity:          for traversing: O(Height)     Space Complexity:         ...

Two Sum problem in a BST || C++ solution

 Two Sum problem in a BST In this problem, a BST and an integer (let k) is given. We have to tell whether we can get the number k by adding the values of BST elements or not. Approach 1: In this approach, we will go to every node and note its value. Now we will traverse the BST to find a value (say t) such that this value plus the noted value equals k. If we get this equal to k, then return true else return false. NOTE:  while searching for t, we will use the property of BST, i.e, if t>node->value then go right else go towards left.     Time Complexity:          In the worst case, we will be traversing the whole BST which takes, O(n)          and for searching: O(height) or O(h)          so overall time complexity: O(n*h)     Space Complexity:          O(1)     C++ Code:      class Solution {      public : ...