dsa / dsa-hashing
22 mins
DSA Module 9: Binary Tree Traversals & Depth
Why This Matters: Binary trees model hierarchical relationships (file systems, HTML DOM, decision trees).
## Tree Traversals & Recursion
Recursive height computation on Binary Trees.
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def max_depth(root: TreeNode) -> int:
if not root:
return 0
return 1 + max(max_depth(root.left), max_depth(root.right))
```
MENTAL MODEL & MEMORY LAYOUT
BINARY TREE STRUCTURE:
( 3 )
/ \
( 9 ) ( 20 )
/ \
( 15 ) ( 7 )
Max Depth = 3 COMMON PITFALLS TO AVOID
- Forgetting base case `if not root: return 0` causing AttributeError on null leaf node access.
Recursive Tree Depth Pattern
# Depth = 1 + max(left_depth, right_depth)
Computes maximum tree depth recursively in O(N) node evaluations.
CONCEPT MASTERY CHECKPOINT
Which tree traversal evaluates root first, then left subtree, then right subtree?
NEXT RECOMMENDED LESSON
DSA Module 10: Heaps & Priority Queues
Challenge: Calculate max depth of binary tree given depth array.