@@honeykumar5700 there is not much difference between preorder and inorder here as the place of print statement of root->val changes in both cases and that is not present here
<a href="#" class="seekto" data-time="549">9:09</a> One small correction If in question it is mentioned B is always present, then no need to check whether root is NULL or not inside solve funtion. Second thing is if it is not present the array ans is anyways going to be empty. So the code is absolutely correct irrespective of the presence of B.
Bhaiya you mentioned that you are using Inorder but I thinks its preorder. Isn't it? Pardon me if am wrong because in code we are checking root first then moving on to left and right which is clearly a preorder (ROOT, LEFT, RIGHT).
Best explanation bhaiya, you are indeed a good teacher and our brother. Love ❤ you bhaiya from the bottom of my heart this series is very good and I hope that in future you also achieve great height of success 👍💯.
if (getpath(root->left, arr, B) || getpath(root->right, arr, B)) return true; if getpath(root->left, arr, B) returns True will it traverse through root->right ??
Being, an 27 year old, @striver @takeUforward content is the only highly impacting and really changing lives of people, I saw till now, thanks BRO, love from Sweden, Europe
Hi Striver, your videos are awesome but in many videos, there's some confusion between inorder & preorder traversals. Like in this video, you said we will be using inorder (Left, Root, Right) but eventually used preorder (Root, Left, Right).
also dont think it is preorder or something else just see this as we neet root first forget about type of traversals they are not for smart people methods it is like spoon feeding
A more beginner friendly solution that I found: bool path(TreeNode* node, int x, vector &ans) {if(node==NULL) return false; if(node->val==x){ ans.push_back(node->val); return true;} bool find_lc=find(node,x,ans); //find if left child has the value if yes push back value if(find_lc){ ans.push_back(node->val); return true;} bool find_rc=find(node,x,ans); //check for right child if(find_rc){ ans.push_back(node->val); return true;} return false;}
This can also be done using iteration . Create map where we store child asindex and parent as value . Do BFS and fill the map . Then we traverse from node to root using the map and put values in a vector . Reverse the vector and return it .
Nicely explained but I found this one a bit complicated . Because I have solved it without complicating it using stack 😀. Followed your words that we don't need to complicate binary tree problems. Btw thanks for such a wonderful series .
you need to also add optimized approaches, iterative in above case, you just make recursive solution videos and in interview we need to come up with optimized approaches as well
@takeUforward isn't it preorder traversal, like at every node we are processing it first and then calling the left subtree and right subtree! Anyways thanks for the awesome solution.
@take U forward Sir I was thinking if we pass vector and NOT vector& we would not need to delete a node's value since every node will now have a local copy of this vector and we can return if we find that node else the whole recursion returns just the starting vector (which will be empty)
I believe its inorder because we check the nodes value itself before traversing the left and right nodes. Thats why in the 7 case shown above we directly return true instead of checking left and right
Time Complexity Doubt : Time Complexity should be O(N*H) where N is number of nodes and H is height of tree. Max Length of ArrayList = O(H) Cost of Remove function in ArrayList = O(H) in the worst case, that is when target is rightmost node, we would be checking each node and for removing the elements from arraylist, O(H) time is spent. Hence Time Complexity = O(N*H) Correct me if I am wrong :)
remove will be O(1) because we always remove the last element from array. You can also use a stack instead, then to remove it will require stack.pop() which is O(1)
At <a href="#" class="seekto" data-time="595">9:55</a> If I had checked for left and right in different if block , would that work , instead of checking them with OR operator ?
I am getting a little confused. Are we implementing in-order or pre-order? At first we are considering the current root, adding it to vector, then we are going to the left and then to the right. I think this is pre order. Please correct me if I am wrong.
Even if node doesn't exist, we don't need to add an extra check since at the end it will return false and finally an empty array. Correct me if I'm wrong 😅
Came up with this messy code, though this problem was easy enough, striver's videos' just help build logic of next videos(ofc spread across playlists as well) bool hasPath(Node *root, vector& prev, int x) { if(!root)return false; prev.push_back(root->data); if(root->data == x) return true; bool t1 = hasPath(root->left,prev,x); bool t2 = hasPath(root->right,prev,x); // if both subtrees do not have the node, pop the cur root if(!t1 and !t2) prev.pop_back(); else return true; return false;// if subtree does not have the node } // function to print the path from root to the // given node if the node lies in the binary tree void printPath(Node *root, int x) { // vector to store the path vector prev; if (hasPath(root, prev, x)) { for (int i=0; i
the solution in video is neither inorder nor preorder, we say is DFS. Here is my preorder Solution: bool rec(TreeNode* node, int x, vector &ans){ if(!node) return false; if(node->val == x) return true; if(rec(node->left, x, ans)) { ans.push_back(node->left->val); return true; } if(rec(node->right, x, ans)) { ans.push_back(node->right->val); return true; } return false; } vector Solution::solve(TreeNode* A, int B) { vector ans; rec(A, B, ans); ans.push_back(A->val); reverse(ans.begin(), ans.end()); return ans; }
