I rarely subscribe to channels, but I did for yours because of how great your teaching method is. It has really helped me better understand data structures and algorithms. Thanks!
Sir ji, apka teaching ka FAN ho gya hu me to .. love you. Some of the best things about your video, 1. your slow explanation. 2. code walk through 3. Complete explanation with lots of examples.
i was not able to understand this question's solution from any other video but your simple explanation worked and i will never forget this solution again, thanks so much sir!
Thank you so much for such a clear explanation. Your explanation not only taught me how to understand walking through the algorithm but it actually taught me how to think about a solution and how to approach the solution. Thanks again.
Sir, I think this is preorder traversal. Because in inorder traversal first we go left then node then right, while in preorder traversal first we go node then left and then right.
Awesome video. Your explanations are simple and clear to understand. Please keep up the good work. For others, just like me if you are bothered about corner case where one of the element is not present in the tree, then try postorder traversal instead of inorder traversal so that you look in to both left and right nodes before coming to root node.
Hello, Thanks for explaining so well, In your logic for finding out LCA works fine if both the nodes are present and both the nodes are part of different sub tree. Two situation does not handle in this code. 1) if either of the node is not present in tree itself 2) if second node is part of subtree of first node. for exm, P and L nodes. If user enters these two nodes then this algorithm will not work. Solution algorithm: 1) Both the nodes must present in tree otherwise print error and return. 2) if left and right returns non NULL, this is LCA. Print LCA and return NULL. 3) if second node is in subtree of first node then only first node we will return till root node. in such case main function shall have a piece of code, if final return is non NULL then this is the LCA, print LCA. I can post the code if someone needs. thanks
good explanations, got tripped by the edge case a bit because this assumes both nodes to be present in the tree, which is fine i guess. In case one of the nodes is not there then it fails.
It would be far better if you also explain the intuition to this solution. Knowing the algorithm makes half of the work but knowing what led to this algorithm will make the solution video totally worthy.
very good explanation , but I think if the any one node either p or q does not exists then your code will fail, we expect to return null as one node is not present in tree. but your code returns the existing value.
A somewhat concise solution which uses the property of BST - LCA's value WILL fall between the the two given nodes. SO you keep going left from root till both the nodes values are less than current node , and keep going right till both value are greater than current value. Below is the code. while(root.data < v1 && root.data < v2){ root = root.right; } while(root.data > v2 && root.data > v1){ root=root.left; } return root;
Great Video. Thank you sir. What happens in the case when there is only one value present in the tree, and the other value is not. In that case, the algorithm is not working.
what if the one of node given to find lca is not present in the tree? i think this solution holds good for both values are present. (if i am not wrong)
Thank you for your tutorial. You are one of the best so far. For the if(left !=null && right = null) return root. Is that right or (right !=null) .Please explain. Thank you very much.
Hi, Does this method will work for "d" and "h" ? ..........what i am thinking is once execution hit "d" then, it will return that node and will never visit "h".
I think so this algorithm will fail when there are multiple occurrences of n1 and n2, @8:06 pause the video see the tree, and replace the following nodes: *h with m, i with r, e with r.* after first finding m and r, node "D" becomes LCA and returns itself to "B", then "B" checks on its right, it finds "R", now on left of "B" we have "D" as LCA and on right of "B" we have "R" as LCA, so it will return "B" as LCA which is wrong, LCA Should have been "D" only.
If one of the nodes p or q does not exist in the Binary Tree, this function will still return the node which is found, but it should have returned NULL. Am I right?
yes Ashok , u r right.....Due to the restriction of space on board , I have just focused on the main condition.....in the code we can modify for this corner condition.....Thanks for helping me get better...!
I wonder when you first encounter this question, how do you figure out the possible steps for getting the answer? I am having trouble of algorithm questions recently. Very hard for me to think of the answer
Awesome vids, can u please consider categorizing ur vids into playlists, for new watchers it helps a lot, otherwise they would have to keep scrolling all ur vids.
Thank you for the explanations. I would like to know how to compute and write the algorithm of the "distance between the node e and node i" in this binary tree.
I mean how to write the algorithm between two nodes (not root node) in a binary. The example with nodes e and i would be useful for me. Thank you in advance.
It is Inorder traversal, as we first check with the current node and return if it is equal to either one. If not equal we expand search to left subtree and right subtree
Actual result comparison happens after both, left and right, return. It is post order. Also, if checking current node first for the result comparison, it should be pre-order, not in-order.
@@badsum Actually, there is both pre and post happening. However, in terms of logic, we check for LCA condition for the current node before checking it left and right subtrees, hence pre. We also do some checking/processing after the children processing. Similar example is when we want to do a sum of all root to leaf paths. In the recursive function, we first add node val to sum so far, then check if we reached a leaf (pre) then return sum, else get sums from left and right child, then add and return those sums (some post).
sir for node k the ancestors are f,c,a and the ancestors of node f are c,a then the common ancestor should be c of nodes k and f but you said the common ancestor is f ?
the lowest common ancestor for parent and its child is the parent itself. I am sorry i have not explained this in the video. I will reply tomorrow again with a more convincing proof. Thanks.
In my interview, the question asked me to return int value.. not node value.. this method just messed.up. pls explain what to do if the function demands returning int value
