Road2Geeks

Clone Graph Problem – DFS Based Solution in Python The Clone Graph problem is a classic graph traversal question where the goal is to create a deep copy of a connected undirected graph. Each node contains a value and a list of its neighboring nodes. The challenge lies in correctly handling cycles and repeated references without creating duplicate nodes or falling into infinite recursion. Problem Overview You are given a reference to a node in a connected undirected graph. Each node has: An integer value val A list of neighboring nodes neighbors Your task is to return a deep copy of the entire graph. Key Insight Graphs can contain cycles, meaning a node can be revisited during traversal. To avoid cloning the same node multiple times, we use a hash map to keep track of already cloned nodes. This solution uses Depth First Search (DFS) with a dictionary called visited : Key → Original node Value → Cloned node DFS-Based Cloning Strate...

Rotting Oranges in Python: DFS vs BFS Explained The Rotting Oranges problem (LeetCode 994) is a classic grid traversal challenge. The task is to determine how many minutes it takes to rot all fresh oranges in a grid given that rotten oranges rot their neighbors in 4 directions every minute. In this article, we will walk through two different approaches to solve this problem in Python: A recursive DFS approach that tracks minimum rot times An optimized and efficient BFS approach using a queue 1. DFS Approach The DFS solution recursively spreads the “rot” from every rotten orange and uses a matrix to keep track of the minimum time taken for each orange to rot. This avoids revisiting oranges unnecessarily and ensures that only the shortest path is used. You can find the complete code here: DFS Solution (LC994_V1.py) class Solution: def rotOranges(self, i, j, itr): if i = self.m or j >= self.n or self.grid[i][j] == 0 or itr > self.answer[i]...

How to Solve “Number of Islands” Using Flood Fill and Graph Traversal When solving grid-based problems, it often feels confusing when explanations suddenly label the problem as a “graph problem” even though no graph is visible. This article explains the Number of Islands problem by connecting it to a much more intuitive idea — the 4-connected flood fill algorithm commonly taught in computer graphics. Problem Overview You are given a 2D grid containing "1" (land) and "0" (water). An island is formed when land cells are connected horizontally or vertically. The task is to count how many such islands exist in the grid. Input: [ ["1","1","0","0"], ["1","0","0","1"], ["0","0","1","1"], ["0","1","0","0"] ] Output: 3 Thinking in Terms of Flood Fill If you have previously implemented floo...

🔍 Problem Overview The task is to find the k-th smallest element in a Binary Search Tree (BST). At first glance, this problem may look like a simple tree traversal problem, but the key insight lies in understanding the special property of a BST. In a BST, an inorder traversal (Left → Root → Right) always visits nodes in sorted order . This property allows us to avoid unnecessary sorting and directly access the k-th smallest element during traversal. 💡 Initial Thought Process My first approach was straightforward: Traverse the entire tree Store all values in a list Sort the list Return the k-th smallest element While this works for any binary tree, it is inefficient for a BST. Once I realized the tree is a BST, I shifted my approach to use inorder traversal, which naturally gives sorted values. 🌳 Recursive Inorder Traversal Approach The idea is to perform an inorder traversal and count nodes as they are visited. Once the count reaches k , we store ...

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...