17. Tree Path Sums & Serialize / Deserialize Binary Tree (Hard) • Data Structures & Algorithms: Blind 75 & Big Tech Interview Prep • Rishabh Ki Kaksha

Data Structures & Algorithms: Blind 75 & Big Tech Interview Prep › 17. Tree Path Sums & Serialize / Deserialize Binary Tree (Hard)

50 mins

← Prev Next →

Course Syllabus

Module 1: Big-O Asymptotics, Arrays & Sliding Window

01. Time & Space Complexity Masterclass: Big-O, Big-Theta, Big-Omega & Amortized Analysis 02. Arrays & Hashing: Two Sum, Contains Duplicate & Valid Anagram (Hash Table Lookups) 03. Prefix Sum & Kadane's Algorithm (Maximum Subarray Problem in O(N)) 04. Sliding Window Pattern: Fixed vs Dynamic Windows (Best Time to Buy/Sell Stock)

Module 2: Two Pointers & Binary Search Systems

05. Two Pointers Pattern: Valid Palindrome, 3Sum & Container With Most Water 06. Binary Search Foundations: Search in Rotated Sorted Array & Find Minimum 07. Binary Search on Answer Space: Koko Eating Bananas & Capacity to Ship Packages

Module 3: Linked Lists & Fast-Slow Pointer Patterns

08. Singly vs Doubly Linked Lists & In-Place Pointer Manipulation (Reverse Linked List) 09. Fast & Slow Pointer (Floyd's Cycle Detection): Linked List Cycle & Middle Node 10. Merging & Reordering: Merge Two Sorted Lists, Reorder List & Remove Nth Node

Module 4: Stacks, Queues & Monotonic Stack Architecture

11. Stack Fundamentals: Valid Parentheses & Min Stack in O(1) Time 12. Monotonic Stack Pattern: Daily Temperatures & Next Greater Element 13. Hard Stack Coding: Largest Rectangle in Histogram & Trapping Rain Water

Module 5: Trees, Binary Search Trees & DFS/BFS Traversals

14. Binary Tree Architecture: Max Depth, Same Tree & Invert Binary Tree 15. BFS Level-Order Traversal & Binary Tree Right Side View 16. Binary Search Tree (BST) Properties: Validate BST & Lowest Common Ancestor (LCA) 17. Tree Path Sums & Serialize / Deserialize Binary Tree (Hard)

Module 6: Heaps, Priority Queues & Top-K Problems

18. Min Heap & Max Heap Internals: Array Representation & Heapify in O(N) 19. Top-K Elements Pattern: Kth Largest Element in an Array & Top K Frequent Elements 20. Two-Heap Pattern: Find Median from Data Stream (Hard)

Module 7: Graphs, Topological Sort & Shortest Paths (Dijkstra)

21. Graph Representations (Adjacency Matrix vs List) & DFS/BFS Traversal 22. Matrix Graph Traversal: Number of Islands, Max Area of Island & Clone Graph 23. Topological Sort (Kahn's Algorithm): Course Schedule I & II (Cycle Detection) 24. Disjoint Set Union (DSU / Union-Find): Redundant Connection & Number of Connected Components

Module 8: Dynamic Programming, Backtracking & Bit Manipulation

25. Backtracking Pattern: Subsets, Permutations, Combination Sum & Word Search 26. 1D Dynamic Programming: Climbing Stairs, House Robber & Coin Change 27. Longest Increasing Subsequence (LIS): O(N^2) DP vs O(N log N) Patience Sort 28. 2D Dynamic Programming: Unique Paths, Longest Common Subsequence (LCS) & Edit Distance 29. 0/1 Knapsack Pattern & Partition Equal Subset Sum 30. Bit Manipulation Tricks: Number of 1 Bits (Hamming Weight), Counting Bits & Missing Number

Interactive Lesson Studio

# 17. Tree Path Sums & Serialize / Deserialize Binary Tree (Hard)

> DSA Blind 75 Notes by Rishabh - Topic 17

---

### 1. LeetCode #124: Binary Tree Maximum Path Sum (Hard 🏆)

*Problem:* Kisi bhi path ka maximum sum find karo (Path kisi bhi node se start aur kisi bhi node par end ho sakta hai).

```python
def maxPathSum(root: TreeNode | None) -> int:
    max_sum = float('-inf')
    
    def gainFromSubtree(node):
        nonlocal max_sum
        if not node:
            return 0
            
        # Ignore negative branches with max(0, ...):
        left_gain = max(gainFromSubtree(node.left), 0)
        right_gain = max(gainFromSubtree(node.right), 0)
        
        # Current node as the highest apex arch of path:
        current_arch_sum = node.val + left_gain + right_gain
        max_sum = max(max_sum, current_arch_sum)
        
        # Return maximum single branch to parent:
        return node.val + max(left_gain, right_gain)
        
    gainFromSubtree(root)
    return max_sum
```

---

### 2. LeetCode #297: Serialize and Deserialize Binary Tree (Hard 📦)

Tree ko string me convert karna aur string se original tree re-construct karna:

```python
class Codec:
    def serialize(self, root: TreeNode | None) -> str:
        res = []
        def dfs(node):
            if not node:
                res.append("N")
                return
            res.append(str(node.val))
            dfs(node.left)
            dfs(node.right)
        dfs(root)
        return ",".join(res)

def deserialize(self, data: str) -> TreeNode | None:
        vals = iter(data.split(","))
        def dfs():
            val = next(vals)
            if val == "N":
                return None
            node = TreeNode(int(val))
            node.left = dfs()
            node.right = dfs()
            return node
        return dfs()
```

---

### 3. Master Comparison Matrix

| Problem | Traversal Used | Key Formula | Complexity |
| :--- | :--- | :--- | :--- |
| **Max Path Sum** | Post-Order DFS | `arch = val + L + R`; `return val + max(L, R)` | $O(N) / O(H)$ |
| **Serialize Tree** | Pre-Order DFS with `"N"` | `[val] + left_res + right_res` | $O(N) / O(N)$ |
| **Path Sum III** | Prefix Sum Hash Map on Trees | `prefix_sum_count[curr_sum - target]` | $O(N) / O(H)$ |

---

### 4. Interview Ke 3 Sawal Is Topic Se

1. **`maxPathSum` me branch return karte waqt `max(0, ...)` kyu lagate hain?** -> Agar kisi subtree ka total sum negative ho (e.g. `-100`), toh us subtree ko include karne ke badle discard (0) karna better hai.
2. **BST ko deserialize karte waqt null markers `"N"` ke bina serialize kiya ja sakta hai kya?** -> Haan! BST ka sirf Pre-order string bina `"N"` ke serialize ho sakta hai kyunki BST properties se ranges $[low, high]$ reconstruct ki ja sakti hain.
3. **Construct Binary Tree from Preorder & Inorder Traversal (LeetCode #105) kaise kaam karta hai?** -> Preorder ka pehla element root hota hai; us root ki Inorder index se Left aur Right subtree ke size divide kiye jaate hain.

---
**Next Topic:** 18. Min Heap & Max Heap Internals: Array Representation & Heapify in O(N)

Loading lesson content...

JavaScript

Live Execution Terminal

Click "Execute Live" to run code.
                