tree-problems.md

Tree Problems

Top-Down

Problem	Difficulty	Notes
94. Binary Tree Inorder Traversal	Easy
965. Univalued Binary Tree	Easy	Compare root, left, right. Or carry root value to check.
872. Leaf-Similar Trees	Easy (1287)
1448. Count Good Nodes in Binary Tree	Medium (1360)
**662. Maximum Width of Binary Tree	Medium	BFS or DFS (with level parameter) + position indexing
**404. Sum of Left Leaves	Easy
1026. Maximum Difference Between Node and Ancestor	Medium (1446)
1315. Sum of Nodes with Even-Valued Grandparent	Medium (1426)
671. Second Minimum Node In a Binary Tree	Easy

Bottom-Up

Problem	Difficulty	Notes
110. Balanced Binary Tree	Easy	Understand why bottom-up DFS.
3319. K-th Largest Perfect Subtree Size in Binary Tree	Medium (1603)
2331. Evaluate Boolean Binary Tree	Easy
**563. Binary Tree Tilt	Easy	Multiple return values.
606. Construct String from Binary Tree	Medium
2265. Count Nodes Equal to Average of Subtree	Medium (1472)
508. Most Frequent Subtree Sum	Medium
1339. Maximum Product of Splitted Binary Tree	Medium (1674)
**1443. Minimum Time to Collect All Apples in a Tree	Medium (1682)	Definition of dfs() and case by case analysis.
**979. Distribute Coins in Binary Tree	Medium (1709)	Direction doesn't matter. Care +/- balance.
1145. Binary Tree Coloring Game	Medium (1741)

• https://leetcode.com/problems/flip-equivalent-binary-trees/description/ 1477
• https://leetcode.com/problems/find-a-corresponding-node-of-a-binary-tree-in-a-clone-of-that-tree/description/ e
• https://leetcode.com/problems/insufficient-nodes-in-root-to-leaf-paths/description/ 1805

Similar problems of 979. Distribute Coins in Binary Tree:

• https://leetcode.com/problems/sum-of-distances-in-tree/description/ 2197
• https://leetcode.com/problems/binary-tree-cameras/description/ 2124

Distance

Problem	Difficulty	Notes
104. Maximum Depth of Binary Tree	Easy
111. Minimum Depth of Binary Tree	Easy
**543. Diameter of Binary Tree	Easy	Definition of dfs(), which edges are counted.
**687. Longest Univalue Path	Medium	Remember to run dfs() in subtree even if it's not univalue.
2246. Longest Path With Different Adjacent Characters	Hard (2126)	Run dfs() in subtree, then check if we can extend the path.
**1376. Time Needed to Inform All Employees	Medium (1560)	How to use Top-down / Bottom-up DFS.
**863. All Nodes Distance K in Binary Tree	Medium (1663)	Parent map and how to prevent revisit.
2385. Amount of Time for Binary Tree to Be Infected	Medium (1711)
1372. Longest ZigZag Path in a Binary Tree	Medium (1713)	Extend or start a new path.
**1530. Number of Good Leaf Nodes Pairs	Medium (1745)	Return distance array or map of node to distance.

Path

Problem	Difficulty	Notes
112. Path Sum	Easy
124. Binary Tree Maximum Path Sum	Hard	maxPathSum is the maximum path sum of the entire tree.
**129. Sum Root to Leaf Numbers	Medium	Carry value down, then return results up.
1022. Sum of Root To Leaf Binary Numbers	Easy (1462)
1457. Pseudo-Palindromic Paths in a Binary Tree	Medium (1405)
988. Smallest String Starting From Leaf	Medium (1429)

Structure

Problem	Difficulty	Notes
100. Same Tree	Easy
572. Subtree of Another Tree	Easy
**652. Find Duplicate Subtrees	Medium	Hashing structure.
1367. Linked List in Binary Tree	Medium	Two pointers matching.
101. Symmetric Tree	Easy
226. Invert Binary Tree	Easy
**617. Merge Two Binary Trees	Easy	Iterative.
**114. Flatten Binary Tree to Linked List	Medium	Flatten subtree first or traverse + flatten in preorder.

Insertion & Deletion

Problem	Difficulty	Notes
814. Binary Tree Pruning	Medium (1380)
1325. Delete Leaves With a Given Value	Medium (1407)
**1110. Delete Nodes And Return Forest	Medium (1511)	Mind the root is not deleted.

Construction

Problem	Difficulty	Notes
2196. Create Binary Tree From Descriptions	Medium (1643)
105. Construct Binary Tree from Preorder and Inorder Traversal	Medium
654. Maximum Binary Tree	Medium	Monotonic stack. (Advanced)

• https://leetcode.com/problems/maximum-binary-tree-ii/description/ 1497
• Solved: https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/description/ m
• https://leetcode.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/ 1731
• https://leetcode.com/problems/recover-a-tree-from-preorder-traversal/ 1797

BFS

Problem	Difficulty	Notes
102. Binary Tree Level Order Traversal	Medium
103. Binary Tree Zigzag Level Order Traversal	Medium
637. Average of Levels in Binary Tree	Easy
513. Find Bottom Left Tree Value	Medium
1161. Maximum Level Sum of a Binary Tree	Medium
199. Binary Tree Right Side View	Medium
116. Populating Next Right Pointers in Each Node	Medium
**993. Cousins in Binary Tree	Easy (1287)
**2641. Cousins in Binary Tree II	Medium (1676)	Sum at level - 1.
**623. Add One Row to Tree	Medium
2471. Minimum Number of Operations to Sort a Binary Tree by Level	Medium (1635)
919. Complete Binary Tree Inserter	Medium (1691)
958. Check Completeness of a Binary Tree	Medium (1703)	We can't have non-null after seeing null.

• https://leetcode.com/problems/binary-tree-level-order-traversal-ii/description/ m
• https://leetcode.com/problems/maximum-level-sum-of-a-binary-tree/description/ m
• https://leetcode.com/problems/find-largest-value-in-each-tree-row/description/ m
• https://leetcode.com/problems/deepest-leaves-sum/description/ 1387
• https://leetcode.com/problems/reverse-odd-levels-of-binary-tree/description/ 1431
• https://leetcode.com/problems/even-odd-tree/description/ 1438
• https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/description/ m

Lowest Common Ancestor

Prerequisites: Bottom-Up

Problem	Difficulty	Notes
236. Lowest Common Ancestor of a Binary Tree	Medium
865. Smallest Subtree with all the Deepest Nodes	Medium (1607)	Find LCA and the depth at the same time.

• https://leetcode.com/problems/step-by-step-directions-from-a-binary-tree-node-to-another/description/ 1805

Serialization

Problem	Difficulty
572. Subtree of Another Tree	Easy
652. Find Duplicate Subtrees	Medium
297. Serialize and Deserialize Binary Tree	Hard

• https://leetcode.com/problems/verify-preorder-serialization-of-a-binary-tree/description/ m

Other

Problem	Difficulty

• Solved: https://leetcode.com/problems/count-complete-tree-nodes/description/, special case of binary tree traversal, more references: https://labuladong.online/algo/data-structure/count-complete-tree-nodes/ + https://programmercarl.com/0222.%E5%AE%8C%E5%85%A8%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E8%8A%82%E7%82%B9%E4%B8%AA%E6%95%B0.html#%E6%80%9D%E8%B7%AF

• https://leetcode.com/problems/find-elements-in-a-contaminated-binary-tree/description/ 1439
• https://leetcode.com/problems/path-in-zigzag-labelled-binary-tree/description/ 1544
• https://leetcode.com/problems/print-binary-tree/
• https://leetcode.com/problems/count-nodes-with-the-highest-score/ 1911
• https://leetcode.com/problems/make-costs-of-paths-equal-in-a-binary-tree/ 1917

三、一般树

3.1 Traversal

• https://leetcode.com/problems/reachable-nodes-with-restrictions/description/ 1476
• https://leetcode.com/problems/reorder-routes-to-make-all-paths-lead-to-the-city-zero/description/ 1633

3.2 Top-Down

• https://leetcode.com/problems/unit-conversion-i/description/
• https://leetcode.com/problems/frog-position-after-t-seconds/description/
• https://leetcode.com/problems/count-pairs-of-connectable-servers-in-a-weighted-tree-network/description/
• https://leetcode.com/problems/maximize-the-number-of-target-nodes-after-connecting-trees-i/description/
• https://leetcode.com/problems/most-profitable-path-in-a-tree/description/

3.3 Bottom-Up

• https://leetcode.com/problems/count-the-number-of-good-nodes/description/
• https://leetcode.com/problems/number-of-ways-to-assign-edge-weights-i/description/
• https://leetcode.com/problems/number-of-nodes-in-the-sub-tree-with-the-same-label/description/
• https://leetcode.com/problems/maximum-number-of-k-divisible-components/description/

Other

TODO: Problem Listing

Backtracking

Problem	Difficulty
257. Binary Tree Paths	Easy
437. Path Sum III	Medium

Explanation

• 662. Maximum Width of Binary Tree
• 543. Diameter of Binary Tree
• 687. Longest Univalue Path
• 2246. Longest Path With Different Adjacent Characters
• 863. All Nodes Distance K in Binary Tree
• 124. Binary Tree Maximum Path Sum
• 1022. Sum of Root To Leaf Binary Numbers
• 572. Subtree of Another Tree
• 652. Find Duplicate Subtrees
• 110. Balanced Binary Tree
• 226. Invert Binary Tree
• 114. Flatten Binary Tree to Linked List
• 297. Serialize and Deserialize Binary Tree
• 236. Lowest Common Ancestor of a Binary Tree