# Introduction - Depth First Search / DFS on Tree

In Using return value (divide and conquer):
Line 7

return should be indented.

Where is the ‘MIN_VAL’ in the divide and conquer approach coming from?
Line 3

I think the tree section in general can use some improvement. This is one of my strongest areas having done nearly 100 tree problems, but I revisited this anyway to review.

Some things that are missing:

1. We should always ask what information we need at the current node to make a decision. This informs your return values. It is the very fundamental mindset to approaching trees and I found it disappointing that it’s not discussed here.
2. We need to be cognizant of pre-order vs. post-order traversal. Pre-order is essentially a greedy way of solving problems - you make the decision before looking at your children. Post-order is the opposite: you make the decision after collecting information on children.

All problems that can be solved with pre-order can be solved with post-order, but the reverse is not true. Also - if a problem can be solved with pre-order, it’s often easier to implement.

Some problems can be solved with either pre-order or post-order traversal. Example: Determine if a tree is a BST. Here you can take 2 approaches: Return the maximum_val, minimum_val, and boolean indicating if a subtree is a bst. Then for the current node, ensure the max_val in left_subtree is less than current node, min_val in right subtree is greater than current node, and ensure both subtrees are also BSTs.

Or you can use pre-order and pass down constraints. E.g. when I go left, pass down the maximum allowed value in my left subtree. When I go right, pass down the minimum allowed value. Then for each node, check if it’s in range.

You can see that pre-order is simpler to implement by far for this problem. But it’s not always possible to use pre-order. For example, find the largest subtree that is also a BST. For this problem it is impossible to use pre-order, only post-order will work.

There should also be a discussion around the following:

• Traversing in reverse:
E.g. In order traversal is Left, Node, Right - so reverse traversal is Right, Node, Left
This also applies to pre-order and post-order. E.g. Post order is Left, Right, Node, and in reverse it’s Node, Right, Left (which is interestingly a modified pre-order traversal)
• Traversing 2 trees simultaneously (e.g. for flipping a tree)
2 Likes

I think every language has a value you can reference to give you the biggest or smallest number they can offer. In Java, it’s Integer.MIN_VALUE and Integer.MAX_VALUE. In Python its float(‘INF’) and float(‘-INF’). You can reference these values when you want to find the max or min of a given group of numbers. It’s possible that the minimum could be a really small negative number, so instead of trying to guess what you should initialize your min-value variable to in the beginning, you can use something like float(‘-INF) or Integer.MIN_VALUE to set it.

what is min_value? wouldnt all nodes reach null and just return min_value?

function dfs(node):
if node is null:
return MIN_VALUE

left_max_val = dfs(node.left)
right_max_val = dfs(node.right)
return max(node.val, left_max_val, right_max_val)

How often does in an interview, does the DFS / questions Related to DFS are been asked to do in iterative method rather than Recursive? Or it is enough to know the recursive way to solve DFS problems ?

This is really interesting, thank you for the info

nice!!

Knowing the recursive is fine.

function dfs(node):
if node is null:
return MIN_VALUE

left_max_val = dfs(node.left)
right_max_val = dfs(node.right)
return max(node.val, left_max_val, right_max_val)

In the above function, the last line’s indentation needs correction.

This is such an amazing writeup. Mod should include this in the article itself.