tree - cocoder39/coco39_LC GitHub Wiki

depth

104. Maximum Depth of Binary Tree (dfs or bfs)
111. Minimum Depth of Binary Tree (dfs or bfs)
110. Balanced Binary Tree (top-down dfs or bottom-up dfs)
366. Find Leaves of Binary Tree (dfs, bottom-up)

tree property

100. Same Tree (recursion + dfs or iteration + stack)
572. Subtree of Another Tree
958. Check Completeness of a Binary Tree
101. Symmetric Tree (dfs + top-down)
222. Count Complete Tree Nodes (dfs)
250. Count Univalue Subtrees (dfs + bottom-up)
333. Largest BST Subtree (250. Count Univalue Subtrees)
1361. Validate Binary Tree Nodes
bsf
- 938. Range Sum of BST

path

112. Path Sum (dfs)
113. Path Sum II (dfs + backtracking)
2246. Longest Path With Different Adjacent Characters
129. Sum Root to Leaf Numbers (dfs)
257. Binary Tree Paths (dfs)
124. Binary Tree Maximum Path Sum (dfs)
543. Diameter of Binary Tree (similar to 124)
1522. Diameter of N‐Ary Tree
298. Binary Tree Longest Consecutive Sequence (dfs)

LCA

236. Lowest Common Ancestor of a Binary Tree (dfs + bottom-up)
235. Lowest Common Ancestor of a Binary Search Tree (bst + top-down)
1644. Lowest Common Ancestor of a Binary Tree II (236 variant)
1650. Lowest Common Ancestor of a Binary Tree III (techniques for intersection of Two Linked Lists)

level order

102. Binary Tree Level Order Traversal (dfs / bfs)
107. Binary Tree Level Order Traversal II
103. Binary Tree Zigzag Level Order Traversal (bfs)
199. Binary Tree Right Side View (dfs / bfs)
314. Binary Tree Vertical Order Traversal (bfs)
987. Vertical Order Traversal of a Binary Tree (either bfs or dfs)
404. Sum of Left Leaves (bfs, dfs)

populating next right pointers

116. Populating Next Right Pointers in Each Node (bfs)
117. Populating Next Right Pointers in Each Node II (bfs + dummy)
Iterative
- inorder
  - 94. Binary Tree Inorder Traversal (iteration / morris)
  - 99. Recover Binary Search Tree (morris)
  - 98. Validate Binary Search Tree (iteration)
  - 173. Binary Search Tree Iterator (iteration)
  - 285. Inorder Successor in BST (recursion / iteration)
  - 272. Closest Binary Search Tree Value II (iteration+deque / stack)
  - 270. Closest Binary Search Tree Value (272. Closest Binary Search Tree Value II)
  - 230. Kth Smallest Element in a BST (iteration / 272. Closest Binary Search Tree Value II)
  - 426. Convert Binary Search Tree to Sorted Doubly Linked List
- preorder
  - 144. Binary Tree Preorder Traversal
  - 331. Verify Preorder Serialization of a Binary Tree
  - 255. Verify Preorder Sequence in Binary Search Tree (monotonic stack, vector mimics stack)
- postorder
  - 145. Binary Tree Postorder Traversal
  - 1443. Minimum Time to Collect All Apples in a Tree
- misc
  - 872. Leaf‐Similar Trees

construct tree

108. Convert Sorted Array to Binary Search Tree (dfs + binary search)
109. Convert Sorted List to Binary Search Tree (bottom-up)
105. Construct Binary Tree from Preorder and Inorder Traversal (dfs)
106. Construct Binary Tree from Inorder and Postorder Traversal (dfs)
1382. Balance a Binary Search Tree (inorder traverse + divide-and-conquer)

reshape

226. Invert Binary Tree (dfs / bfs)
114. Flatten Binary Tree to Linked List (preorder, morris / dfs+bottom-up)
156. Binary Tree Upside Down (recursion / iteration)

Serialization/De-serialization

297. Serialize and Deserialize Binary Tree (pre-order, construct, reshape)
428. Serialize and Deserialize N ary Tree
449. Serialize and Deserialize BST
536. Construct Binary Tree from String

divide-and-conquer