// return non-null return value from the recursive calls
Node left = dfs(root.left, target)
if (left != null) {
return left;
}
Why not just do: return dfs(root.left, target); instead?
Then you are not going to check to right sub tree.
can you have the visualization of the stack also horizontal? I visualize it better that way
what will be the return value of this block?
I agree, why not just return dfs(root.left, target); instead?
I went through the the example, and the value of “left” was always null in the end, and the condition on the line 6 never checked.
pre-order traversal was covered in introduction to tree data structure module. I think the assumption is that you are covering the topics in order (no pun).
This recursive stack call animation is amazing.
Internet reference is saying that DFS can be done using InOrder, preOrder or PostOrder and most popular variant is InOrder. The course here says that DFS is essentially PreOrder. Why so much discrepancies in concepts?
academically, it can be in many orders. in real interview questions, you almost always do in order. especially for backtracking and dynamic programming problems. we simply the concept here for easier understand.
Very nice visualization!
Yet, I can’t understand what happens when a null node is reached (right after visiting node with key = 3). It follows from the visualuzation that after returning to the node with key = 3, the dfs() function decides to check the right node. How does it know that it is time to check the right node?
Can some one explain
Why there is
if left is not None:
return left
As in Preorder DFS we check the value of the root, move to left child, check value, move to left child and so on the whole way down the side of the tree until we hit a leaf or end node, in which we then move to root.right
Left is returned so as to still have access to the root node when the recursive calls comes back, allowing us to go root .right
left becomes root in the next recursion call,
step 1 → root = node 1, check if node 1 == target, left = node, dfs(left) if left is not None else dfs(right)
@ mod: in your comment you said “in real interview questions, you almost always do in order”! WAIT… Did you mean to say " pre order"?? Because, the above article/blog suggests to use “Pre order for DFS”! Request to clarify : do you typically recommend DFS via pre order or in order ??
How is backtracking being implemented by the example code (Python)? When it gets to 5 and root.left and root.right are both None, wouldn’t the whole function have returned None there?
To answer for anyone potentially wondering the same, the confusion is wrapping your head around how recursion returns values.
Our code does the following checks in order:
def dfs(root, target):
1- if root is None:
return None
2- if root.val == target:
return root
3- left = dfs(root.left, target)
4- if left is not None:
return left
5- return dfs(root.right, target)
1- Is the value at the current Node null? If so, return immediately.
2- Is the value at the current Node equal to our target? If so, return immediately
3- Since the value at the current node is not null (from Step 1), go down the left branch
4- We’ve returned from checking the left branch, if the value isn’t null, return it.
5- The value that has been returned from from the left branch was null, return the value obtained from going down the right branch, whether it’s null or not null.
Essentially how we got to 5 from 1 is as follows:
We have the first instance of our dfs function. We’ll refer to it as dfs-1. dfs-1 starts going down its 5 steps:
1- Current node isn’t null, move onto step 2.
2- Current value isn’t equal to target, move onto step 3.
3- Go down the left node, call another dfs function to do this.
Now we have two functions in stack memory, dfs-1, and dfs-2 which we just created that’s on Node 2.
dfs-1’s execution is still on its Step 3, it’s frozen there until it gets a return from dfs-2.
dfs-2 starts going through its steps, and gets to its own Step 3, it now freezes there and creates dfs-3 and waits till it gets a return from dfs-3.
dfs-3 is on Node 3.
dfs-3 execution goes till it gets to its own Step 3, it now freezes there and creates dfs-4, and waits till it gets a return from it.
So our chain right now is dfs-1 is waiting on dfs-2 which is waiting on dfs-3 which is waiting on dfs-4.
dfs-4’s value is null, since the left node of Node 3 is null. dfs-4 goes to Step 1, see’s it’s null, and immediately returns null back to dfs-3.
dfs-3 can now progress to Step 4. The value it received from dfs-4 is null, so it proceeds to Step 5, returning the value from the right branch. This is where the trickiness happens. Unlike Step 3, we are immediately returning the value from right branch traversal in Step 5.
So when dfs-3 now creates a new recursion call, let’s call it dfs-5 for traversing down the right node, whenever dfs-5 returns to dfs-3, dfs-3 will immediately return to dfs-2, and dfs-2 will unfreeze and move past its Step 3.
So to answer watermelon’s question, when it gets to Node 5 and root.right is None, it will immediately return back None to the right traversal call of Node 5, which immediately returns back None to the right traversal call of Node 3, which immediately returns back None to the left traversal call of Node 2. Node 2 then continues onto Step 4, etc…
i think the “if” part is to return back the target value.