Binary Search Tree
Problems
Right now problems are taken from geeksforgeeks.org. After sometime, more resources will be covered. Thanks geeksforgeeks.org in advance.
Q. Given an array of N elements and two integers A, B which belongs to the given array. Create a Binary Search Tree by inserting element from arr[0] to arr[n-1]. The task is to find the maximum element in the path from A to B
Analysis: Time Complexity: If BST is not balanced O(n) else O(logn) Space Complexity: Extra Space needed is O(1) Space needed for Recursion: If BST is not balanced then O(n) else O(logn) Q. Given a Balanced Binary Search Tree (BST), write a function isTripletPresent() that returns true if there is a triplet in given BST with sum equals to 0, otherwise returns false. Sol: https://www.geeksforgeeks.org/find-if-there-is-a-triplet-in-bst-that-adds-to-0/ As an optimization one thing can be done do a tree traversal and find whether at least one negative element is present in the tree. Tricky part is converting BST to doubly linked list which takes O(nlogn) time Analysis: Time Complexity of core logic: O(n^2) Space Complexity: Extra Space needed is O(1) Space needed for Recursion: If BST is not balanced then O(n) else O(logn) Q. Given a Binary Tree, write a function that returns the size of the largest subtree which is also a Binary Search Tree (BST). If the complete Binary Tree is BST, then return the size of whole tree. Sol: https://www.geeksforgeeks.org/find-the-largest-subtree-in-a-tree-that-is-also-a-bst/ Analysis: Space Complexity: Extra Space needed is O(1) Space needed for Recursion: If BST is not balanced then O(n) else O(logn) Q. Given an array of integers, replace every element with the least greater element on its right side in the array. If there are no greater element on right side, replace it with -1. Sol: https://www.geeksforgeeks.org/replace-every-element-with-the-least-greater-element-on-its-right/ Analysis: Space Complexity: Extra Space needed is O(n) Space needed for Recursion: If BST is not balanced then O(n) else O(logn)
Q. Two of the nodes of a Binary Search Tree (BST) are swapped. Fix (or correct) the BST.
Sol: https://www.geeksforgeeks.org/fix-two-swapped-nodes-of-bst/
Time Complexity of core logic: O(n)
Space Complexity:
Extra Space needed is O(1) Space needed for Recursion: If BST is not balanced then O(n) else O(logn) Q. Count inversions in an array
Analysis:
Time Complexity of core logic: O(nlogn)
Space Complexity: Extra Space needed is O(n) Q. Given a stream of integers, lookup the rank of a given integer x. Rank of an integer in stream is “Total number of elements less than or equal to x (not including x)”. Sol: https://www.geeksforgeeks.org/rank-element-stream/
Analysis: You can use C++, upper_bound and equal_range.
Time Complexity of core logic: O(nlogn)
Space Complexity: Extra Space needed is O(1)
Q. Given a Preorder traversal of a Binary Search Tree. The task is to print leaf nodes of the Binary Search Tree from the given preorder.
Sol: https://www.geeksforgeeks.org/leaf-nodes-preorder-binary-search-tree/
Analysis: You can use C++, upper_bound and equal_range.
Time Complexity of core logic: O(n)
Space Complexity: Recursion stack size O(n) Extra Space needed is O(1) Q. Given a Postorder traversal of a Binary Search Tree. The task is to print leaf nodes of the Binary Search Tree from the given postorder. Sol:
Q. Given a inorder traversal of a Binary Search Tree. The task is to print leaf nodes of the Binary Search Tree from the given inorder.
ReferencesSol:
Q. Given a Preorder traversal of a Binary Search Tree. The task is the inorder of the Binary Search Tree.
Sol:
#include
using namespace std;
void pretoinorder(int src[], int* &tar, int s, int e, int& ti) {
if (s > e)
return;
int x;
for (x = s+1; x <= e; x++) {
if (src[x] > src[s])
break;
}
pretoinorder(src, tar, s+1, x-1, ti);
tar[ti] = src[s];
ti++;
pretoinorder(src, tar, x, e, ti);
}
int main(int argc, char** argv) {
int s[] = {10, 5, 4, 6, 15, 12, 17};
int n = sizeof (s)/sizeof(s[0]);
int *t = new int[sizeof (s)];
int ti = 0;
pretoinorder(s, t, 0, n-1, ti);
for (int i = 0; i < n; i++) {
cout << " target[" << i << "] = " << t[i] << endl;;
}
}
Analysis:
Time Complexity of core logic: O(n)
Space Complexity: Recursion stack size O(n)
Extra Space needed is O(n)
Sol:
#include
using namespace std;
void pretopostorder(int src[], int* &tar, int s, int e, int& ti) {
if (s > e)
return;
int x;
for (x = s+1; x <= e; x++) {
if (src[x] > src[s])
break;
}
pretopostorder(src, tar, s+1, x-1, ti);
pretopostorder(src, tar, x, e, ti);
tar[ti] = src[s];
ti++;
}
int main(int argc, char** argv) {
int s[] = {10, 5, 4, 6, 15, 12, 17};
int n = sizeof (s)/sizeof(s[0]);
int *t = new int[sizeof (s)];
int ti = 0;
pretopostorder(s, t, 0, n-1, ti);
for (int i = 0; i < n; i++) {
cout << " target[" << i << "] = " << t[i] << endl;;
}
}
Analysis:
Time Complexity of core logic: O(n) Space Complexity: Recursion stack size O(n)
Extra Space needed is O(n)
Q. Given a postorder traversal of a Binary Search Tree. The task is to find the prerder of the Binary Search Tree.
Sol:
using namespace std; void posttoinorder(int src[], int* &tar, int s, int e, int& ti) { if (s > e) return; int x; for (x = s; x < e; x++) { if (src[x] > src[e]) break; } posttoinorder(src, tar, s, x-1, ti); tar[ti] = src[e]; ti++; posttoinorder(src, tar, x, e-1, ti); } int main(int argc, char** argv) { int s[] = {4, 6, 5, 12, 17, 15, 10}; int n = sizeof (s)/sizeof (s[0]); int *t = new int[sizeof (s)]; int ti = 0; posttoinorder(s, t, 0, n-1, ti); for (int i = 0; i < n; i++) { cout << " target[" << i << "] = " << t[i] << endl;; } }
Analysis:
Time Complexity of core logic: O(n) Space Complexity: Recursion stack size O(n)
Extra Space needed is O(n)
Q. Given a postorder traversal of a Binary Search Tree. The task is to find the inorder of the Binary Search Tree.
Sol:
#include
using namespace std;
void posttopreorder(int src[], int* &tar, int s, int e, int& ti) {
if (s > e)
return;
int x;
for (x = s; x < e; x++) {
if (src[x] > src[e])
break;
}
tar[ti] = src[e];
ti++;
posttopreorder(src, tar, s, x-1, ti);
posttopreorder(src, tar, x, e-1, ti);
}
int main(int argc, char** argv) {
int s[] = {4, 6, 5, 12, 17, 15, 10};
int n = sizeof (s)/sizeof (s[0]);
int *t = new int[sizeof (s)];
int ti = 0;
posttopreorder(s, t, 0, n-1, ti);
for (int i = 0; i < n; i++) {
cout << " target[" << i << "] = " << t[i] << endl;;
}
}
Analysis:
Time Complexity of core logic: O(n) Space Complexity: Recursion stack size O(n)
Extra Space needed is O(n)
Q. You are given an array of n integer and an integer K. Find the number of total unordered pairs {i, j} such that absolute value of (ai + aj – K), i.e., |ai + aj – k| is minimal possible where i != j.
Time Complexity of core logic: O(nlogn)
Space Complexity:
Extra Space needed is O(n)
Q. Level order traversal of Binary Tree. Sol: Use 1 queue Time Complexity: O(n) Space complexity: O(2^(n-1)) Q. Reverse Level order traversal of Binary Tree. Sol: Use queue of queues. Follow similar to above and keep enqueing the queues to queue of queues. Once all elements are consumed, start dequeing quques one by one and print each element of every queue. Time Complexity: O(n) Space complexity: O(n)
Q. Zig zag level order traversal of Binary Tree.
Sol: Use 2 stacks. For first stack push the children in left to right order and for second stack push the children in right to left order. Time Complexity: O(n) Space complexity: O(n)
Q. Reverse Zig zag level order traversal of Binary Tree.
Sol: Use stack of stacks. Follow similar to above and keep pushing the stacks to stack of stacks. Once all elements are consumed. the pop stacks one by one and print each element of every stack. Time Complexity: O(n) Space complexity: O(n) https://www.geeksforgeeks.org/ |
Comments
Post a Comment