Trees / DFS Pattern: LeetCode Guide & Problems (2026)

Problem	Difficulty	Companies	Freq	Solution
Invert Binary Tree #Tree #DFS #BFS	Easy	AmazonApple +1	High	Solution
Maximum Depth of Binary Tree #Tree #DFS #BFS	Easy	AmazonLinkedIn	High	Solution
Validate Binary Search Tree #Tree #DFS #BST	Medium	AmazonBloomberg +2	High	Solution
Lowest Common Ancestor of a BST #Tree #DFS #BST	Medium	AmazonFacebook +1	High	Solution
Binary Tree Maximum Path Sum #Tree #DFS #DP	Hard	AmazonFacebook +2	High	Solution
Serialize and Deserialize Binary Tree #Tree #DFS #BFS	Hard	GoogleAmazon +2	Medium	Solution
Diameter of Binary Tree #Tree #DFS #Binary Tree	Easy	FacebookAmazon +1	High	Solution
Symmetric Tree #Tree #DFS #BFS	Easy	AmazonMicrosoft +1	High	Solution
Binary Tree Right Side View #Tree #DFS #BFS	Medium	FacebookAmazon +1	High	Solution
Kth Smallest Element in a BST #Tree #DFS #BST	Medium	AmazonFacebook +1	High	Solution
Construct Binary Tree from Preorder and Inorder Traversal #Array #Hash Table #Divide and Conquer	Medium	AmazonMicrosoft +1	Medium	Solution
Path Sum II #Backtracking #Tree #DFS	Medium	AmazonMicrosoft +1	Medium	Solution
Count Good Nodes in Binary Tree #Tree #DFS #BFS	Medium	FacebookAmazon	Medium	Solution
Flatten Binary Tree to Linked List #Linked List #Stack #Tree	Medium	AmazonMicrosoft +1	Medium	Solution
Sum Root to Leaf Numbers #Tree #DFS #BFS	Medium	AmazonGoogle +1	Medium	Solution
Populating Next Right Pointers in Each Node #Linked List #Tree #DFS	Medium	FacebookAmazon +1	Medium	Solution
Same Tree #Tree #Depth-First Search #Breadth-First Search	Easy	AmazonGoogle +1	High	Solution
Subtree of Another Tree #Tree #Depth-First Search #String Matching	Easy	AmazonFacebook +1	High	Solution

🧠

Mastering the Trees / DFS Pattern for Coding Interviews

1. Mental Model & Visual Intuition

The Trees / DFS pattern is designed to eliminate redundant work and reduce search spaces. Rather than evaluating every possible state using a naive brute-force approach, this pattern relies on an invariant that allows you to safely discard subproblems that cannot lead to an optimal answer. When encountering an interview question, look for core triggers such as monotonicity, contiguous constraints, optimal substructure, or overlapping subproblems.

2. Algorithmic Invariants & Step-by-Step Execution

To implement this pattern flawlessly under interview conditions, structure your thought process into three discrete steps:

State Initialization: Define your boundaries, pointers, or memoization tables clearly before entering loops.
State Transition: Update tracking variables incrementally as new elements enter or leave your active evaluation window.
Feasibility Check: When constraints are violated, systematically shrink or adjust your state until the valid invariant is restored.

3. Time and Space Complexity Trade-Offs

In top-tier technical interviews at Google, Meta, and Amazon, arriving at a working solution is only half the battle. You must explicitly justify why your approach achieves optimal Big-O bounds. For Trees / DFS, the target time complexity is typically O(n) — visits each node once while maintaining an auxiliary space complexity of O(h) where h is height; O(n) worst case (skewed). Always discuss whether an in-place modification or two-pass traversal can save memory.

4. Common Interview Edge Cases to Test

Before informing your interviewer that you have completed coding, trace your logic against these standard high-failure test cases:

Empty inputs, single-element collections, or all-identical values.
Inputs with negative numbers, duplicates, or extreme values that could cause integer overflow.
Odd versus even length inputs when dealing with pointer convergence or tree midpoints.