codementor on Nostr: Both are O(n) time: each node is visited once. The level version holds one full level ...

Both are O(n) time: each node is visited once.

The level version holds one full level in memory. In a balanced tree the last level has about n/2 nodes, so that is O(n).

The recursive version uses the call stack: O(height). That is O(log n) for a balanced tree, but O(n) for a chain, where deep recursion can even overflow the stack.

The result itself is O(n) either way, so in an interview both answers are fine. Just name the trade-off.

#tg003 · TG-003-A3