Trees / DFS

Recursive and iterative depth-first traversal for tree structure problems.

16 problems 4 Easy 10 Medium 2 Hard

Overview

Tree DFS leverages the recursive nature of trees. Most tree problems have elegant recursive solutions. Understanding pre-order, in-order, and post-order traversals is fundamental.

When to Use

Tree height/depth
Path sum problems
Lowest common ancestor
Validate BST
Serialize/deserialize tree
Symmetric tree / mirror

Common Mistakes

Forgetting the base case for null nodes
Confusing pre/in/post order traversal
Stack overflow on very deep trees — consider iterative DFS

Complexity

Time

O(n) — visits each node once

Space

O(h) where h is height; O(n) worst case (skewed)

// Generic DFS template
function dfs(node) {
  if (!node) return; // base case

  // Pre-order: process node here
  dfs(node.left);
  // In-order: process node here
  dfs(node.right);
  // Post-order: process node here
}

// Path sum
function hasPathSum(root, target) {
  if (!root) return false;
  if (!root.left && !root.right) return root.val === target;
  return hasPathSum(root.left, target - root.val) ||
         hasPathSum(root.right, target - root.val);
}

Problems (16)

Hide completed

Problem	Difficulty	Companies	Freq
Invert Binary Tree	Easy	AmazonApple +1	High
Maximum Depth of Binary Tree	Easy	AmazonLinkedIn	High
Validate Binary Search Tree	Medium	AmazonBloomberg +2	High
Lowest Common Ancestor of a BST	Medium	AmazonFacebook +1	High
Binary Tree Maximum Path Sum	Hard	AmazonFacebook +2	High
Serialize and Deserialize Binary Tree	Hard	GoogleAmazon +2	Medium
Diameter of Binary Tree	Easy	FacebookAmazon +1	High
Symmetric Tree	Easy	AmazonMicrosoft +1	High
Binary Tree Right Side View	Medium	FacebookAmazon +1	High
Kth Smallest Element in a BST	Medium	AmazonFacebook +1	High
Construct Binary Tree from Preorder and Inorder Traversal	Medium	AmazonMicrosoft +1	Medium
Path Sum II	Medium	AmazonMicrosoft +1	Medium
Count Good Nodes in Binary Tree	Medium	FacebookAmazon	Medium
Flatten Binary Tree to Linked List	Medium	AmazonMicrosoft +1	Medium
Sum Root to Leaf Numbers	Medium	AmazonGoogle +1	Medium
Populating Next Right Pointers in Each Node	Medium	FacebookAmazon +1	Medium

Trees appear in nearly every FAANG interview. Here's every tree pattern — DFS, BFS, LCA, BST, path p…

Enjoying this free content?

If this saved you time, buying me a coffee keeps new content coming.

☕ Buy me a coffee

Buy me a coffee