Construct binary search tree from preorder traversal | Leetcode
HTML-код
- Опубликовано: 16 ноя 2024
- This video explains a very important programming interview problem which is to construct a binary search tree or BST from given preorder traversal. I have explained 2 approaches for this problem. The first approach is a very simple algorithm to construct BST in just O(N2) time.This is the simplest of all methods.I have also explained the intuition behind solving this problem by explaining examples and BST property. The second approach is a much more optimized algorithm which solves the problem in just O(N) time.I have explained both the approaches by taking suitable examples and finally i have explained CODE for both the methods. BOTH CODEs are present in the same LINK given below. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
CODE LINK: gist.github.co...
This guy voice really pumps me to code💪💪
❤️
I did something slightly different. For every array i knew that the first element would be the root and the first element higher than that (lets call it mid) would be the beginning of the right side of that root. We would then look for the left side in [begin + 1, mid - 1] and the right in [mid, end]. I think that this should be O(N**2) if the tree is not balanced (for instance [10 9 8 7 6 5 ...]).
This is similar to using next greater element technique. Nice idea nonetheless :)
Coming at you at supersonic speed
12:12 🙏
😅
lol
/*
OPTIMAL APPROACH: Using rec
Time Complexity: O(n), n => no. of nodes which is stored in arr
Space Complexity: O(n), rec depth which is height
*/
class Solution {
TreeNode* buildBST(vector& A, int& i, int bound) {
if (i == A.size() || A[i] > bound)
return NULL;
TreeNode* root = new TreeNode(A[i++]);
root->left = buildBST(A, i, root->val);
root->right = buildBST(A, i, bound);
return root;
}
public:
TreeNode* bstFromPreorder(vector& preorder) {
int i = 0;
return buildBST(preorder, i, INT_MAX);
}
};
5:18 I think it should be (nlogn) instead of (n^2) as it takes (logn) time to find position of a element in BST , so for n element it should take (nlogn).
It is not a self balanced BST and so the tree can become skewed for ASC or DSC order elements. Therefore, it will be O(N^2).
@@techdose4u oh!
Thanks Sir for correcting me.
@@techdose4u exactly what i was searching for. Thank you.
worst case analysis is O(N^2) but average case is O(nlogn) I think the average case is more representative of its true growth rate with random data set
excellent..please continue making these videos
Thanks....I will
Well explained, thank you!
Welcome :)
you don t have tp talk that fast in the end . good stuff
😅
Great explanation. Thank you so much!
Thank you so much sir :)
Welcome 😀
12:12 till end, faster than mutual fund ads declaimer :P
Please make videos for Leetcode Problem set 105 and 106
👍🏼
Nice way of teaching in less time . Please make a video on 'Data Structures'.
👍sure
Bro you are best .....
Pretty smooth
Please do in python. Its very hard to unserstand in cpp.
def bstFromPreorder(self, preorder: List[int]) -> TreeNode:
tree = TreeNode(preorder[0])
def insert(tree: TreeNode, val: int) -> TreeNode:
if val > tree.val:
if tree.right is not None:
return insert(tree.right, val)
else:
tree.right = TreeNode(val)
else:
if tree.left is not None:
return insert(tree.left, val)
else:
tree.left = TreeNode(val)
return tree
for v in preorder:
if v == tree.val:
continue
else:
insert(tree, v)
return tree
The second answer time complexity will be O(nlogn) instead of O(3*n) = O(n) here the constant was 3 because log 8 = 3. Please correct me if I am wrong
You are incorrect. You saw 3 because in the worst case, we will come to a node 3 times. Once from parent and twice by returning from child. It has nothing to do with number of nodes. I hope you got it.
@@techdose4u thanks a lot I understand it now
Welcome :)
please make a playlist for graph data structures
You will see it from 1st week of may :)
@@techdose4u bro will the playlist contain all questions of graph important one that is asked in MNCs
thanks
Welcome :)
sir, plz make a video on sort an array element by frequency
Use map
can you please explain why did you pass the root by reference (TreeNode* &root)? I am unable to get it.
Did u got answer abt this ?
To pass the actual address(reference) of the root and not just the root pointer....Otherwise it would copy the nodes inside memory everytime.
TreeNode* buildBst(TreeNode* &root, int x) // In formal arguments, why root is sent using a '&' sign...someone plz explain !!
To pass the actual address(reference) of the root and not just the root pointer....Otherwise it would copy the nodes inside memory everytime.
Node *construct(int pre[],int &i, int minval,int maxval,int n){
if(i>=n) return NULL;
Node * root = NULL;
int val = pre[i];
if(val > minval and val < maxval){
root = newNode(val);
i++;
root->left = construct(pre,i,minval,val,n);
root->right = construct(pre,i,val,maxval,n);
}
return root;
}
Node* constructTree(int pre[], int size) {
int i = 0;
return construct(pre,i,INT_MIN,INT_MAX,size);
}
In Optimised solution,
If input is 10, 5, 1, 7, 2, 40, 50
It prints 1 5 7 10
It does't go back to the left subtree. Isn't it wrong ?
declare pos as pointer or public variable so it can change continuously
I am getting same problem like. You
Can we make use of queue ? Plz make a video is possible
Sir, what is meant by null in the passed vector and how it is handled in your code?
Yea it has been handled by returning NULL.
@@techdose4u bt sir in your optimised code where are you handling with null. I am not getting help me
Finding size of vector and returning NULL if size is 0. Check in main fn.
@@techdose4u we are iterating over the vector what will happen if we encounter null in middle of vector as given in the sample test case
@@ManojKrVerma-vw4dx input array(vector) won't be having null as an element. Because input array is array of int. No need to handle it.
Why can't we just print the elements in level order traversal after arranging in bst.
LeetCode wants you to return the root of the binary tree structure. When you return it, it will call a print function to print out the values of the tree in level order traversal. So just return the correct tree and don't worry about the output
Yes Oscar is correct.
@@ElephantSoup ooooo ..thanks a lot for pointing it out.
Man, I am able to solve easy level questions but switching to medium level questions seems impossible. I have solved around 280 problems including leetcode, codechef, hackerrank, and codeforces. I have taken the data structure class last semester. Would you please recommend something?
Why so long code when you can do it without upperbound in O(N)
class Solution {
int i = 0;
public TreeNode bstFromPreorder(int[] arr) {
return helper(arr, Integer.MAX_VALUE);
}
public TreeNode helper(int[] arr, int bound) {
if (i == arr.length || arr[i] > bound) return null;
TreeNode root = new TreeNode(arr[i++]);
root.left = helper(arr, root.val);
root.right = helper(arr, bound);
return root;
}
}
Sir
134,345,1,4,2,9
Is input ke liye ye optimised code kam nhi krega
I think you need to check this code again
Someone please correct me if I am wrong
Output- 134 345
Which is not correct output
There is voting happening in a college to select an amendment, total 16 professor and there are 4 groups each group consists of 4 prof and for an amendment to be selected it should be, first selected atleast by a single professor in each group and finally select the one which appears maximum times.
sir what is question about if possible please explanation sir. it is asked in amazon
this problem seems to be a variation of celebrity problem (stack), check that once.
*JAVA Solution :)*
class Solution {
public TreeNode helper(ArrayList arr) {
if (arr.size() == 0)
return null;
int rootData = arr.get(0);
TreeNode root = new TreeNode(rootData);
if (arr.size() == 1)
return root;
ArrayList smaller = new ArrayList();
ArrayList greater = new ArrayList();
for (int i : arr) {
if (i < rootData) smaller.add(i);
else if (i > rootData) greater.add(i);
}
root.left = helper(smaller);
root.right = helper(greater);
return root;
}
public TreeNode bstFromPreorder(int[] preorder) {
int n = preorder.length;
ArrayList arr = new ArrayList(n);
int i = 0;
while (arr.size() < n)
arr.add(preorder[i++]);
return helper(arr);
}
}
I think this one is better and more polished than the code explained in the video.
Btw your videos are very helpful keep doing this noble work....:)
.