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:
- 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.
- 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)
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
thank you, very helpful.
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.
thanks for the additional information!
“ask what information we need at the current node to make a decision” is discussed in 2. Identify state(s) (passing value down from parent to child)
the pre-order vs post-order == return value vs. global variable section
This was interesting, thanks for sharing it !