Back to Hub
Module 04

Binary Trees, DFS/BFS & LCA

Interview Cheat Sheet — Binary Trees, DFS/BFS & LCA

Time: O(N) · Space: O(H) or O(W)

Pattern Triggers

Use tree traversals for hierarchical data and parent-child dependencies: Level-Order BFS for shortest depth or level views, Post-Order DFS for bottom-up subtree aggregation, and split-point bubbling for Lowest Common Ancestor (LCA).

Core Invariant

Always define what a recursive call returns upward (such as subtree height or a matched target node) separately from what it updates globally (such as maximum diameter passing through the current node).

Complexity

Time: O(N) because each node is visited once. Space: O(H) for the DFS recursion stack (O(log N) balanced, O(N) skewed) or O(W) for the BFS queue (maximum tree width).

Diameter of Binary Tree (Post-Order DFS)
INITIALIZING
Step 1 / 12
Step Breakdown
INIT

Loading...

DiameterOfBinaryTree.kt
Shortcuts: Left / Right Step · Space Play/Pause · R Reset