Tree DFS

Question 1

What is the pattern and when is Tree DFS used?

Answer 1

Explores tree depth-first via recursion or stack.

Use Case: Path finding, pre/post/inorder traversal.

Example: [Binary Tree Inorder Traversal]. Action: Verbalize use case aloud.

Question 2

What are the key steps in Tree DFS?

Answer 2

1. Process node (preorder) or recurse left/right.
2. Recurse left, process (inorder), recurse right.
3. Process after recursion (postorder).

Action: Explain steps for [Binary Tree Inorder Traversal] aloud.

Question 3

How does Tree DFS apply to [Binary Tree Inorder Traversal]?

Answer 3

Return inorder traversal of binary tree.
Approach: Recurse left, process node, recurse right.

Example: [Binary Tree Inorder Traversal]. Action: Verbalize solution logic aloud.

Question 4

What are the complexity and gotchas of Tree DFS?

Answer 4

Time: O(n), Space: O(h), h=height.

Gotchas: Empty tree, unbalanced tree.

Action: List edge cases for [Binary Tree Inorder Traversal] aloud.

Question 5

Code example for Tree DFS.

Answer 5

```python
from typing import Optional, List
class TreeNode:
def __init__(self, val: int = 0, left: ‘TreeNode’ = None, right: ‘TreeNode’ = None) -> None:
self.val = val
self.left = left
self.right = right
def inorder_traversal(root: Optional[TreeNode]) -> List[int]:
result: List[int] = []
def dfs(node: Optional[TreeNode]) -> None:
if not node:
return
dfs(node.left)
result.append(node.val)
dfs(node.right)
dfs(root)
return result
~~~