🧠
Iterative DFS Using Stack
💡 This approach replaces recursion with an explicit stack to simulate DFS, helping avoid recursion stack overflow and demonstrating iterative tree traversal.
Intuition
Use a stack to traverse nodes depth-first, tracking the depth of each node explicitly, and update the maximum depth encountered.
Algorithm
- Initialize a stack with the root node and its depth as 1.
- While the stack is not empty, pop a node and its depth.
- Update the maximum depth if current depth is greater.
- Push the node's children onto the stack with depth + 1.
💡 Tracking depth explicitly is key here, which can be tricky for beginners used to recursion.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def maxDepth(root):
if root is None:
return 0
stack = [(root, 1)]
max_depth = 0
while stack:
node, depth = stack.pop()
if node:
max_depth = max(max_depth, depth)
stack.append((node.left, depth + 1))
stack.append((node.right, depth + 1))
return max_depth
# Example usage:
if __name__ == '__main__':
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20, TreeNode(15), TreeNode(7))
print(maxDepth(root)) # Output: 3
Line Notes
if root is None:Handle empty tree edge case
stack = [(root, 1)]Initialize stack with root node and depth 1
node, depth = stack.pop()Pop current node and its depth for processing
max_depth = max(max_depth, depth)Update max depth if current depth is larger
import java.util.Stack;
public class Solution {
public static class TreeNode {
int val;
TreeNode left, right;
TreeNode(int val) { this.val = val; }
}
public int maxDepth(TreeNode root) {
if (root == null) return 0;
Stack<Pair<TreeNode, Integer>> stack = new Stack<>();
stack.push(new Pair<>(root, 1));
int maxDepth = 0;
while (!stack.isEmpty()) {
Pair<TreeNode, Integer> current = stack.pop();
TreeNode node = current.getKey();
int depth = current.getValue();
if (node != null) {
maxDepth = Math.max(maxDepth, depth);
stack.push(new Pair<>(node.left, depth + 1));
stack.push(new Pair<>(node.right, depth + 1));
}
}
return maxDepth;
}
// Simple Pair class since Java 8+ doesn't have built-in Pair
public static class Pair<K,V> {
private K key;
private V value;
public Pair(K key, V value) { this.key = key; this.value = value; }
public K getKey() { return key; }
public V getValue() { return value; }
}
public static void main(String[] args) {
Solution sol = new Solution();
TreeNode root = new TreeNode(3);
root.left = new TreeNode(9);
root.right = new TreeNode(20);
root.right.left = new TreeNode(15);
root.right.right = new TreeNode(7);
System.out.println(sol.maxDepth(root)); // Output: 3
}
}
Line Notes
if (root == null) return 0;Handle empty tree
Stack<Pair<TreeNode, Integer>> stack = new Stack<>();Initialize stack to hold nodes with their depths
Pair<TreeNode, Integer> current = stack.pop();Pop node and depth for processing
maxDepth = Math.max(maxDepth, depth);Update max depth if current depth is greater
#include <iostream>
#include <stack>
#include <utility>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
int maxDepth(TreeNode* root) {
if (root == nullptr) return 0;
stack<pair<TreeNode*, int>> stk;
stk.push({root, 1});
int max_depth = 0;
while (!stk.empty()) {
auto [node, depth] = stk.top();
stk.pop();
if (node) {
max_depth = max(max_depth, depth);
stk.push({node->left, depth + 1});
stk.push({node->right, depth + 1});
}
}
return max_depth;
}
int main() {
TreeNode* root = new TreeNode(3);
root->left = new TreeNode(9);
root->right = new TreeNode(20);
root->right->left = new TreeNode(15);
root->right->right = new TreeNode(7);
cout << maxDepth(root) << endl; // Output: 3
return 0;
}
Line Notes
if (root == nullptr) return 0;Handle empty tree case
stack<pair<TreeNode*, int>> stk;Stack stores nodes paired with their depth
auto [node, depth] = stk.top();Unpack node and depth from stack top
max_depth = max(max_depth, depth);Update max depth if current depth is larger
function TreeNode(val, left = null, right = null) {
this.val = val;
this.left = left;
this.right = right;
}
function maxDepth(root) {
if (root === null) return 0;
const stack = [[root, 1]];
let maxDepth = 0;
while (stack.length > 0) {
const [node, depth] = stack.pop();
if (node !== null) {
maxDepth = Math.max(maxDepth, depth);
stack.push([node.left, depth + 1]);
stack.push([node.right, depth + 1]);
}
}
return maxDepth;
}
// Example usage:
const root = new TreeNode(3,
new TreeNode(9),
new TreeNode(20, new TreeNode(15), new TreeNode(7))
);
console.log(maxDepth(root)); // Output: 3
Line Notes
if (root === null) return 0;Handle empty tree
const stack = [[root, 1]];Initialize stack with root and depth 1
const [node, depth] = stack.pop();Pop node and depth for processing
maxDepth = Math.max(maxDepth, depth);Update max depth if current depth is greater
Each node is visited once, so time is O(n). The stack can hold up to the height h of the tree, so space is O(h).
💡 This approach avoids recursion but uses similar memory proportional to tree height.
Interview Verdict: Accepted
This iterative approach is equally efficient and useful when recursion depth is a concern.