76 articles
Week 1 of the FAANG mock interview program pairs easy and medium problems from arrays and trees. The goal is not ceiling testing — it is installing the think-aloud habits that distinguish passing candidates before difficulty ramps up in week 2.
The complete binary tree interview playbook for 2026 — 9 patterns, ready-to-paste DFS/BFS templates, and a curated index of 75 LeetCode tree problems asked at Google, Meta, Amazon, Apple, and Microsoft.
LeetCode 104 — Maximum Depth of Binary Tree, asked by Amazon, Google, Meta and Apple as a phone-screen warmup. Solve it in one line of recursive DFS or with iterative BFS level counting in O(n) time.
LeetCode 226 — Invert Binary Tree, the famous Max Howell / Google whiteboard rejection question. Solve recursively in 4 lines or iteratively with BFS in O(n) time.
LeetCode 101 — Symmetric Tree, asked at Amazon, Microsoft and Bloomberg. Compare opposite subtrees with a two-pointer recursive helper to check mirror symmetry in O(n) time.
LeetCode 112 — Path Sum, asked at Amazon, Microsoft, Apple and Meta. Use DFS with a running remainder to detect any root-to-leaf path that sums to a target value in O(n) time.
LeetCode 100 — Same Tree, asked at Amazon, Meta, Google and Apple. Walk both trees simultaneously and return false on the first structural or value mismatch in O(n) time.
LeetCode 110 — Balanced Binary Tree, asked at Amazon, Meta, Google and Microsoft. Use a postorder DFS that returns -1 on imbalance to solve it in O(n) time instead of the naive O(n log n).
LeetCode 617 — Merge Two Binary Trees, asked at Amazon, Apple, Meta and Microsoft. Walk both trees in parallel, sum overlapping nodes, and reuse existing pointers in O(n) time.
LeetCode 938 — Range Sum of BST, asked at Amazon, Facebook (Meta), Google and Apple. Use the BST property to prune entire out-of-range subtrees and run in O(h + k) time.
LeetCode 700 — Search in a BST, asked at Amazon, Microsoft, Apple and Meta. Eliminate half the tree at each step using the BST property and finish in O(h) time, O(1) iterative space.
LeetCode 102 — Binary Tree Level Order Traversal, asked at Amazon, Meta, Google and Microsoft. The canonical BFS template that powers Right Side View, Zigzag, Largest in Each Row and 30+ other problems.
LeetCode 103 Binary Tree Zigzag Level Order Traversal — frequently asked at Amazon, Meta, Microsoft, and Bloomberg. Learn the BFS toggle pattern with deque appendleft for O(n) time.
LeetCode 199 Binary Tree Right Side View — high-frequency at Amazon, Meta, Google, and Apple. Two clean approaches: BFS taking last node per level and DFS visiting right-first.
LeetCode 113 Path Sum II — Medium tree backtracking favorite at Amazon, Meta, Microsoft. Collect every root-to-leaf path summing to target with DFS plus path append-and-pop.
LeetCode 543 Diameter of Binary Tree — top Tree DP problem at Amazon, Meta, Google, Bloomberg. Single DFS that returns height while tracking the longest path through any node.
LeetCode 98 Validate Binary Search Tree — high-frequency at Amazon, Meta, Google, Apple. Pass min and max bounds down through DFS so every node is strictly within its valid range.
LeetCode 230 Kth Smallest Element in a BST — Amazon, Meta, Uber favorite. Iterative inorder with a stack stops at the kth pop in O(h+k) time.
LeetCode 236 Lowest Common Ancestor of a Binary Tree — Amazon, Meta, Google, Apple favorite. Single post-order DFS that returns root when either target is found, then propagates the split point upward.
LeetCode 235 Lowest Common Ancestor of a Binary Search Tree — top BST problem at Amazon, Meta, Microsoft. Iterative O(h) navigation with O(1) space using BST ordering.
LeetCode 105 Construct Binary Tree from Preorder and Inorder Traversal — Amazon, Google, Microsoft favorite. Divide-and-conquer with a HashMap for O(1) inorder lookup giving O(n) total time.
LC 437 Path Sum III counts all paths in a binary tree summing to a target. The optimal O(n) solution mirrors the subarray sum equals k trick — use a prefix sum frequency map with DFS backtracking, a pattern tested at Amazon and Google.
LC 450 Delete Node in a BST is a top FAANG interview problem testing all three deletion cases. Master the in-order successor strategy to pass BST questions at Amazon, Google, and Microsoft.
LC 114 Flatten Binary Tree to Linked List rearranges a binary tree into a right-skewed linked list in pre-order. The optimal O(1) space solution uses a Morris-like pointer manipulation trick tested at Amazon and Microsoft.
LC 116 Populate Next Right Pointers asks you to connect each node to its next right sibling. The O(1) space solution leverages already-connected next pointers on the current level to wire up the next level — a pattern tested at Amazon and Microsoft.
LC 863 All Nodes Distance K in Binary Tree finds all nodes exactly K edges from a target. The key insight is converting the tree to an undirected graph by recording parent pointers, then running BFS from the target — a pattern tested at Amazon and Google.
Solve LeetCode 129 Sum Root to Leaf Numbers with the carry-and-accumulate DFS pattern asked at Meta, Amazon, Google, and Microsoft. Includes Python and JavaScript code, dry run, and follow-ups.
Solve LeetCode 662 Maximum Width of Binary Tree with the heap-style index trick used in Amazon, Meta, and Microsoft interviews. Includes overflow-safe BFS code in Python and JavaScript.
Solve LeetCode 1448 Count Good Nodes in Binary Tree with the DFS carry-max pattern asked at Microsoft, Meta, and Amazon. Includes Python and JavaScript code, complexity analysis, and FAANG-style follow-ups.
Solve LeetCode 538 Convert BST to Greater Tree using reverse in-order traversal asked at Google, Microsoft, and Amazon. Single O(n) pass with O(h) space.
Solve LeetCode 652 Find Duplicate Subtrees with postorder serialization and hashing — a Google and Amazon favorite. Includes Python and JavaScript solutions with O(n^2) and O(n) approaches.
Generate all structurally unique BSTs storing values 1 to n using recursion plus memoization. LeetCode 95 is asked at Google, Amazon, and Meta to test divide-and-conquer reasoning on Catalan-number-sized search spaces.
Trim a BST so all values lie within [low, high] using recursive subtree pruning. LeetCode 669 is a Medium FAANG question asked at Amazon, Google, and Apple.
Encode a BST compactly using preorder traversal without null markers and rebuild it with min-max bounds. LeetCode 449 is a Medium FAANG question asked at Amazon, Google, and Meta.
Solve LeetCode 987 Vertical Order Traversal using DFS coordinates plus tie-breaking sort. A Hard FAANG question asked at Meta, Amazon, and Google.
Solve LeetCode 2096 by finding LCA, building path strings, and replacing the start path with U moves. Asked at Amazon, Meta, and Google for FAANG-style tree pathing.
Verify a binary tree is complete with one BFS pass. Once a null child is encountered, every subsequent dequeued node must be null. LeetCode 958 is a Medium FAANG question asked at Amazon, Meta, and Microsoft.
Recover a BST where two nodes are swapped using in-order traversal to find the inversion pair. LeetCode 99 is asked at Amazon, Google, and Meta. Includes O(1) space Morris traversal solution.
LC 337 House Robber III extends the classic House Robber DP to a binary tree where adjacent nodes cannot both be robbed. The optimal O(n) solution uses post-order DFS returning a (rob, skip) pair — a fundamental tree DP pattern tested at Amazon and Microsoft.
LC 968 Binary Tree Cameras asks for the minimum number of cameras to monitor all nodes. The O(n) greedy solution assigns three states per node in a bottom-up DFS — delay camera placement as high as possible, a pattern tested at Amazon and Google.
LC 979 Distribute Coins in Binary Tree asks for minimum moves to give each node exactly one coin. The O(n) solution tracks coin excess flowing through each edge via post-order DFS — a pattern tested at Amazon and Google that elegantly converts a counting problem into a flow problem.
LC 1483 Kth Ancestor of a Tree Node answers each query in O(log k) after O(n log n) preprocessing using binary lifting — a sparse table DP technique that also powers LCA algorithms and is commonly tested at Amazon.
LC 124 Binary Tree Maximum Path Sum finds the highest-value path in a binary tree where the path can start and end at any node. The O(n) solution uses a post-order DFS that tracks the global max while returning only one branch to the parent — a critical FAANG interview problem at Amazon, Google, and Facebook.
LC 297 Serialize and Deserialize Binary Tree is a top FAANG hard problem asked at Facebook, Amazon, and Google. The DFS preorder approach with null markers gives a compact O(n) codec; BFS level-order is more intuitive. Both are valid interview answers.
LC 1373 Maximum Sum BST in Binary Tree finds the highest sum among all BST subtrees of a binary tree. The O(n) solution uses post-order DFS returning a 4-tuple of (is_bst, min, max, sum) metadata — a hard FAANG problem tested at Amazon and Google.
LC 1008 Construct BST from Preorder Traversal reconstructs a binary search tree in O(n) using min-max bounds to decide left vs right placement — a clean recursion problem tested at Amazon and Google that showcases BST property exploitation.
LC 366 Find Leaves of Binary Tree groups nodes by their height (distance from the nearest leaf) using a post-order DFS — a problem asked at Amazon and LinkedIn that reveals an elegant alternative to iterative leaf removal.
Count nodes in a complete binary tree in O(log^2 n) by comparing left and right spine heights to detect perfect subtrees and skip counting them entirely.
Find the minimum seconds to collect all apples in an undirected tree using post-order DFS — include a subtree path only when it contains at least one apple.
Find the maximum |a - b| for any ancestor-descendant pair by tracking the running minimum and maximum along every root-to-leaf path during DFS.
Find the longest zigzag path in a binary tree by DFS — track the current direction and length, reset when the direction breaks, and update a global maximum.
LeetCode 834 Sum of Distances in Tree is a Google and Meta favorite hard problem solved in O(n) using two-pass DFS with the rerooting technique on an undirected tree.
LeetCode 96 Unique Binary Search Trees asks for the count of structurally unique BSTs storing 1..n. Solve it in O(n^2) using Catalan number DP — a favorite Amazon and Google interview question.
LeetCode 429 N-ary Tree Level Order Traversal is a level-by-level BFS over a tree where each node has any number of children. Common at Amazon and Meta as a BFS warmup.
LeetCode 814 Binary Tree Pruning removes every subtree that contains no 1. Solve it in O(n) using post-order recursion — a classic Amazon and Google interview question.
LeetCode 1161 Maximum Level Sum returns the smallest level whose node-sum is largest. Solve in O(n) with BFS level-size snapshots — a common Amazon and Meta phone-screen question.
LeetCode 988 Smallest String Starting From Leaf returns the lexicographically smallest leaf-to-root string. Solve in O(n * h) using DFS with path strings — popular at Amazon and Google.
LeetCode 2385 Amount of Time for Binary Tree to Be Infected models tree-to-graph BFS spread. Solve in O(n) by converting to an undirected graph and running BFS from the start node — common at Amazon, Google, and Meta.
LeetCode 2471 Minimum Number of Operations to Sort a Binary Tree by Level uses BFS plus minimum-swaps-to-sort-an-array. Solve in O(n log n) — a popular Google and Meta interview question.
LeetCode 173 BST Iterator implements a controlled inorder traversal with O(h) memory and amortized O(1) next. Asked at Amazon, Google, Meta, and Apple as a class-design tree question.
LeetCode 666 Path Sum IV reconstructs a tree from depth-position-value encoded integers and returns the sum of all root-to-leaf paths. Solve with hashmap DFS in O(n) — frequent at Amazon and Alibaba.
LeetCode 272 (Hard) frequently asked at Google and Meta. Use BST inorder traversal to get a sorted list, then a two-pointer shrink window selects the k closest values to a target in O(n) time.
LeetCode 156 (Medium) classically asked at Google and LinkedIn. Re-root a binary tree by flipping each left child into the new parent and the original parent into the new right child, in O(n) time and O(1) extra space iteratively.
LeetCode 510 (Medium) frequently asked at Microsoft and Facebook. Find the inorder successor of a BST node when each node has a parent pointer, in O(h) time and O(1) extra space without access to the root.
LeetCode 671 (Easy) asked at Amazon and Lyft. Find the second minimum value in a special binary tree where every node equals the min of its children, using DFS with pruning in O(n) time.
LeetCode 606 (Easy) asked at Amazon and Apple. Serialize a binary tree in preorder with parentheses, omitting empty parens only when they do not affect the one-to-one mapping, in O(n) time.
LeetCode 623 (Medium) asked at Amazon and Microsoft. Insert a new row of value v at a given depth, pushing existing children down as left/right subtrees of new nodes, using BFS or DFS in O(n) time.
LeetCode 1302 (Medium) asked at Amazon and Oracle. Sum all node values at the deepest level of a binary tree using BFS level-order traversal in O(n) time and O(w) space.
LC 993 Cousins in Binary Tree checks if two nodes are at the same depth with different parents. The clean O(n) BFS solution processes one level at a time — a foundational tree problem tested at Amazon and Microsoft.
LC 222 Count Complete Tree Nodes has an O(log^2 n) solution that exploits perfect subtree detection — a FAANG interview problem where the naive O(n) answer is wrong. Learn the left/right spine height comparison trick tested at Amazon and Google.
LC 701 Insert into a BST traverses left or right based on value comparisons until finding a null position. The O(h) recursive solution is a BST fundamentals question tested at Amazon and Microsoft — always insert at a leaf.
LC 589 N-ary Tree Preorder and LC 590 Postorder Traversal generalize binary tree DFS to trees with any number of children. These easy problems build the foundation for harder n-ary tree problems asked at Amazon and Google.
LC 427 Construct Quad Tree builds a spatial partitioning tree from a 2D binary grid by recursively splitting non-uniform regions into four quadrants. This divide-and-conquer problem is tested at Amazon and Google and models real-world image compression and spatial indexing.
LeetCode 897 (Easy). Rebuild a BST into a strictly right-skewed list using a single inorder traversal that rewires left and right pointers in place.
LeetCode 2265 (Medium). Count every node whose value equals the floor average of its own subtree using a single postorder DFS that returns sum and count to the parent.
Complete recap of the Trees DSA section covering 9 reusable patterns, complexity tables, and a problem index mapped to LeetCode favorites at FAANG interviews.