Tree algorithms.
Understand the recursion, follow each branch, then put it into code.
Traversals
| Problem | Difficulty | Time complexity | Practice |
|---|---|---|---|
| Preorder Traversal | Easy | O(n) | LeetCode |
| Inorder Traversal | Easy | O(n) | LeetCode |
| Postorder Traversal | Easy | O(n) | LeetCode |
| Level Order Traversal | Easy | O(n) | LeetCode |
| Zigzag Level Order | Medium | O(n) | LeetCode |
| Morris Inorder Traversal | Medium | O(n) | LeetCode |
Tree properties
| Problem | Difficulty | Time complexity | Practice |
|---|---|---|---|
| Maximum Depth (Height) | Easy | O(n) | LeetCode |
| Check a Balanced Binary Tree | Easy | O(n) | LeetCode |
| Diameter of a Binary Tree | Easy | O(n) | LeetCode |
| Maximum Path Sum | Hard | O(n) | LeetCode |
| Symmetric Tree | Easy | O(n) | LeetCode |
| Invert a Binary Tree | Easy | O(n) | LeetCode |
| Count Complete Tree Nodes | Medium | O(log² n) | LeetCode |
Paths & ancestors
| Problem | Difficulty | Time complexity | Practice |
|---|---|---|---|
| Root-to-Leaf Paths | Easy | O(n + L) | LeetCode |
| Root-to-Leaf Path Sum | Easy | O(n) | LeetCode |
| Lowest Common Ancestor | Medium | O(n) | LeetCode |
| Nodes at Distance K | Medium | O(n) | LeetCode |
Views
| Problem | Difficulty | Time complexity | Practice |
|---|---|---|---|
| Right Side View | Medium | O(n) | LeetCode |
| Boundary Traversal | Medium | O(n) | GFG |
| Vertical Order Traversal | Hard | O(n log n) | LeetCode |
Binary search trees
| Problem | Difficulty | Time complexity | Practice |
|---|---|---|---|
| Search in a BST | Easy | O(h) | LeetCode |
| Insert into a BST | Medium | O(h) | LeetCode |
| Delete from a BST | Medium | O(h) | LeetCode |
| Validate a BST | Medium | O(n) | LeetCode |
| Kth Smallest in a BST | Medium | O(h + k) | LeetCode |
Construction
| Problem | Difficulty | Time complexity | Practice |
|---|---|---|---|
| Build from Preorder & Inorder | Medium | O(n) | LeetCode |
| Serialize & Deserialize | Hard | O(n) | LeetCode |
| Flatten to a Linked List | Medium | O(n) | LeetCode |