Road2Geeks

Binary Tree Level Order Traversal — Python Solution Level Order Traversal is one of the fundamental tree traversal techniques where we visit every node of a binary tree level by level, starting from the root and moving left-to-right within each level. It’s widely used in breadth-first search (BFS) patterns and is a staple in algorithm interviews. :contentReference[oaicite:0]{index=0} 💡 What is Level Order Traversal? Given the root of a binary tree, the goal is to return a nested list where each sublist represents all node values at that specific level of the tree. For example, for the binary tree: Input: root = [3,9,20,null,null,15,7] 3 / \ 9 20 / \ 15 7 The expected traversal output is: [ [3], [9,20], [15,7] ] 📌 Idea Behind the App...

Invert Binary Tree (LeetCode 226) Invert Binary Tree is one of the most popular beginner-friendly problems when starting with tree recursion. The task is simple: for every node in the binary tree, swap its left and right children. However, many beginners struggle not with swapping — but with writing the correct base case . This post walks through an initial incorrect approach, explains why it fails, and then breaks down the correct recursive solution. ❌ First Attempt (Incorrect Base Case) Here was my first approach when solving this problem: class Solution: def invertTree(self, root): if not root.left or not root.right: return root self.invertTree(root.left) self.invertTree(root.right) root.left, root.right = root.right, root.left return root Why this fails The condition below causes the function to return too early: if not root.left or not root.right: return root This stops recursion whenever a n...

Maximum Depth of Binary Tree (LeetCode 104) When I started solving tree problems, I had absolutely no idea how to approach them. This was my first tree problem, so I initially watched a YouTube video to understand the intuition. After that, I explored three different ways to solve the problem. In this post, I’ll explain all three approaches in a simple and beginner-friendly manner. 📌 Problem Statement Given the root of a binary tree, return its maximum depth. Maximum Depth is the number of nodes along the longest path from the root node down to the farthest leaf node. 🧠 Approach 1: Recursive Depth-First Search (DFS) This is the most natural way to solve tree problems because trees are recursive by nature. For every node, we calculate the depth of its left and right subtrees and take the maximum. class Solution: def maxDepth(self, root): if not root: return 0 return 1 + max(self.maxDepth(root.left), self.maxD...

Greedy Pattern: Erase Overlapping Intervals (LeetCode 435) Some problems quietly test whether you recognize a classic greedy pattern . Erase Overlapping Intervals is one of them. At first glance, it feels like an interval-merging problem. But once you pause and think — the real objective becomes clear: Remove the minimum number of intervals so that the remaining intervals do not overlap. Problem Restatement Given an array of intervals where intervals[i] = [start, end] , return the minimum number of intervals you need to remove to make the rest non-overlapping. Key Insight (Pattern Recognition) Instead of asking: Which intervals should I remove?

Insert Interval (LeetCode 57) The Insert Interval problem looks simple at first glance, but it tests how well you understand interval overlapping and edge cases. The goal is to insert a new interval into a list of already sorted, non-overlapping intervals and merge where necessary — all while maintaining the sorted order. 🧠 Key Observations The intervals are already sorted by start time. There are only three possible cases while traversing intervals. We can process everything in a single pass. 📌 Three Possible Cases Current interval is completely after newInterval → Insert newInterval and append the rest. Current interval is completely before newInterval → Just add it to the result. Overlapping intervals → Merge by expanding newInterval . 🧪 Example Intervals = [[1,3],[6,9]] New Interval = [2,5] Output = [[1,5],[6,9]] 💡 Python Implementation class Solution: def insert(self, intervals, ne...

Merge Intervals – Problem Overview The Merge Intervals problem is a classic greedy + sorting problem that frequently appears in coding interviews. Given a list of intervals, the task is to merge all overlapping intervals and return the non-overlapping result. Key Intuition The core idea is simple but powerful: First, sort all intervals by their start time Then, merge intervals only when they overlap with the previous one Once the intervals are sorted, any overlapping interval must be adjacent. This allows us to solve the problem in a single linear scan after sorting. Step-by-Step Approach Sort the intervals based on the starting value Initialize the result list with the first interval Iterate through the remaining intervals If the current interval overlaps with the last merged interval, update the end boundary If it does not overlap, start a new interval Python Implementation class Solution: def merge(self, intervals: List...

Problem Overview The Largest Rectangle in Histogram problem is one of those classic questions that looks simple but exposes gaps in pattern recognition very quickly. You are given an array where each element represents the height of a bar in a histogram, and your task is to find the area of the largest rectangle that can be formed. Initially, I had no intuition for this problem. I could brute-force it mentally, but nothing scalable came to mind. Only after revisiting monotonic stacks again did the solution start making sense. Key Insight Instead of trying to form rectangles explicitly, flip the thinking: Assume each bar is the shortest bar in the rectangle. Once you do that, the only thing you need to know is: The nearest smaller bar on the left The nearest smaller bar on the right Between these two boundaries, the current bar can safely extend and form a rectangle. This transforms the problem into finding previous smaller and next smaller elements — a ...