Keep up the good work. This is the best explanation I've seen. I was surprised to see you only have 4.37k subscribers. If you keep this up I think you'll get a lot more subscribers in the future!
Hi algo, last question, ...say for eg the overall left_depth was 2 not 1, then how can we put left_depth as 2 right at the end when we return, if the last value for the left_depth variable was 1(from the right hand side of the tree which was the value returned to node 3)?
In depth first search, we would traverse the entire left side of the tree first before ever moving on to the right side. So it doesn't matter what's on the right side of the tree. The overall left depth (2 in your example) would be set as the left_depth variable in the function call where node 1 is the root. Then the algorithm would proceed down the right side to find the right_depth.
Hi Algo, at 6.02 mins in the video, how can the left_depth now be set to 1?? I dont get how the value 1 is being stored in the left_depth function call. any help would be greatly appreciated
Let's start at 5:53. We are currently in the function where the purple node is "root", and we will be returning 1 + the maximum of the left depth and right depth of the purple node. They are both 0, so we'll return 1 + 0 = 1. So we return to the function where the ORANGE node is the root, and we return right where we left off on the line of code with the orange dot. On that line, maxDepth(root.left) is the function that we are returning from, so we return the value of 1 and assign it to the left_depth variable.
thanks for getting back to me, i just dont get how when you return max(Left_d,epth or Right _depth) how does it know which function call Left_ depth or Right_depth, to send the value too . is it because the last function call in the stack is yellow(left_depth) and so it knows that it was a left_depth , and then assigns that value to the left_depth variable?? @@AlgoEngine
@@Richard-yz2gy It's because the last function call in the stack was maxDepth(root.left) from this line with the orange dot: left_depth = maxDepth(root.left) Which means whatever is returned from maxDepth(root.left) will be stored in the left_depth variable. In this case, we return 1 so 1 is stored in left_depth. If this is still confusing to you, it might be better to review recursion concepts first, then come back to this problem.
@@AlgoEngine Sure yes, but isn't there any effect on time and space complexity because of recursion? Can you direct to any resource to get a better understanding of how recursion or DP effects the time and space complexity.
@@sbrahma0 The effect of recursion becomes relevant when talking about the space complexity. We will need to allocate space for each recursive call for each node, but we will never need to simultaneously hold memory for nodes on the same level (since if we wanted to visit another node on the same level, we would exit that recursive call and free that memory, go back up the tree, and then allocate memory for a new recursive call). Therefore, if the height of the tree is h, then the most amount of space needed at a time is O(h). As a consequence, if the tree is balanced, then the space complexity becomes O(log n). If the tree is completely unbalanced, then the space complexity degrades to O(n). Here is a nice article that does a deeper dive on tree traversals: www.enjoyalgorithms.com/blog/binary-tree-traversals-preorder-inorder-postorder
