Checking if Two Binary Trees are Identical

Day - 99 Insert into a Binary Search Tree The problem - Given the root node of a binary search tree (BST) and a value to insert into the tree, return the root node of the BST after the insertion. It is guaranteed that the new value does not exist in the original BST. Note that there may exist multiple valid ways for the insertion, as long as the tree remains a BST after insertion. Brute Force - Perform inorder traversal to collect all values, add the new value, sort the array, then rebuild the BST from the sorted array. This gives O(n log n) time complexity due to sorting and is unnecessarily complex since BST properties allow direct insertion. Approach Used - •) If root == null, return new TreeNode(val), found the insertion position. •) If root.val > val, value is smaller, insert in left subtree, root.left = insertIntoBST(root.left, val). •) Else (when root.val < val), value is larger, insert in right subtree, root.right = insertIntoBST(root.right, val). •) Return root. Complexity - Time - O(h), where h = height of tree. Space - O(h), recursion stack depth. Note - BST insertion leverages the binary search property: compare the value with current node, go left if smaller, right if larger. Recursively traverse until finding an empty position (null), then create and return the new node. The recursion naturally updates parent pointers as it backtracks, maintaining tree structure without explicit parent tracking. #DSA #Java #SoftwareEngineering #InterviewPrep #LearnToCode #CodeDaily #ProblemSolving

Started the Merge Sort section today. Before understanding the full algorithm, the first thing was learning how to merge two already sorted arrays into one sorted array. This small piece of logic is actually the core operation behind Merge Sort. Things that became clear : - using two pointers to traverse both arrays - always placing the smaller element first - continuing until both arrays are fully processed - overall time complexity becomes O(m + n) Main merge logic : static void merge(int[] a, int[] b, int[] c) { int i = 0, j = 0, k = 0; while (i < a.length && j < b.length) { if (a[i] <= b[j]) c[k++] = a[i++]; else c[k++] = b[j++]; } while (i < a.length) c[k++] = a[i++]; while (j < b.length) c[k++] = b[j++]; } What seemed like a small helper function is actually the heart of Merge Sort, because the entire algorithm depends on merging smaller sorted pieces correctly. Understanding this step made the later recursion part much easier to follow. Continuing deeper into Merge Sort and divide-and-conquer next. #dsa #algorithms #mergesort #sorting #java #learninginpublic

Most people would return this answer: [2, 2] But the correct answer is: [2] Why? 🚀 Day 64/365 — DSA Challenge Solved: Intersection of Two Arrays The task: Given two arrays, return their intersection. But there are two conditions: • The element must exist in both arrays • The result must contain only unique values Example: nums1 = [1,2,2,1] nums2 = [2,2] Output: [2] Even though 2 appears multiple times, it should appear only once in the result. 💡 My Approach (Simple Logic) Step 1 Loop through every element of nums1. Step 2 Check if that number exists in nums2. Step 3 Before adding it to the result, make sure it hasn't already been added. To keep the code clean, I used three methods: intersection() Main method that loops through nums1 and builds the result. existsInArray(num, arr) Checks if a number exists in another array. existsInArray(num, arr, length) Checks duplicates only inside the filled part of the result array. Example walkthrough: 1 -> not in nums2 -> skip 2 -> exists -> add 2 -> already added -> skip 1 -> skip Final output: [2] ⏱ Time Complexity: O(n × m) 📦 Space Complexity: O(n) Day 64/365 complete. Code 👇 https://lnkd.in/dad5sZfu #DSA #Java #LeetCode #LearningInPublic #ProblemSolving #Consistency

Day - 104 Recover Binary Search Tree The problem - You are given the root of a binary search tree (BST), where the values of exactly two nodes of the tree were swapped by mistake. Recover the tree without changing its structure. Follow up: A solution using O(n) space is pretty straight forward. Could you devise a constant O(1) space solution? Brute Force - Perform inorder traversal to collect all values in an array, identify the two swapped elements, store their positions, traverse the tree again to find and swap them back. This gives O(n) time and O(n) space for storing all node values. Approach Used - •) Declare first (first swapped node), second (second swapped node), prev (previous node in inorder traversal). •) Call helper function, helper(root). •) Swap the values, temp = first.val, first.val = second.val, second.val = temp. Helper Function - helper(TreeNode node) •) If node == null, return. •) Traverse left subtree, helper(node.left). •) If prev != null AND prev.val > node.val, - If first == null, set first = prev. - ⁠Set, second = node. •) Update, prev = node. •) Traverse right subtree, helper(node.right). Complexity - Time - O(n), where n is number of nodes. Space - O(h), recursion stack depth. Note - In a valid BST, inorder traversal produces a sorted sequence. When two nodes are swapped, it creates violations where prev.val > current.val. For adjacent swaps, there's one violation; for non-adjacent swaps, there are two. By tracking the first and second violating nodes during inorder traversal, we identify the swapped pair. The algorithm handles both cases by always updating second and only setting first once. #DSA #Java #SoftwareEngineering #InterviewPrep #LearnToCode #CodeDaily #ProblemSolving

🔥 Day 96 of #100DaysOfCode Today’s problem: LeetCode – Find Minimum in Rotated Sorted Array 🔄📉 📌 Problem Summary You are given a sorted array that has been rotated at some pivot. Example: Sorted array → [1,2,3,4,5] Rotated → [3,4,5,1,2] Goal 👉 Find the minimum element in the array. Example: Input: [3,4,5,1,2] Output: 1 🧠 Approach: Binary Search Since the array was originally sorted, we can use Binary Search to locate the rotation point. Key observation: If nums[l] < nums[r] → Subarray is already sorted → Minimum is nums[l] Otherwise: Compute middle index Compare with left boundary to decide which half to search ⚙️ Decision Logic 1️⃣ If left part is sorted → Minimum must be in right half 2️⃣ If left part is not sorted → Minimum is in left half 💡 Key Idea We are essentially searching for the rotation pivot, which contains the smallest value. ⏱ Time Complexity: O(log n) 💾 Space Complexity: O(1) 🚀 Performance Runtime: 0 ms Beats 100% submissions 🔥 Memory: 43.8 MB 🧠 Pattern Insight Common Binary Search variants: Search in Rotated Sorted Array Find Minimum in Rotated Array Peak Element Binary Search on Answer Recognizing these patterns makes solving them much faster. Only 4 days left to complete #100DaysOfCode 🚀 Consistency paying off every day. On to Day 97 🔥 #100DaysOfCode #LeetCode #BinarySearch #RotatedArray #Java #DSA #InterviewPrep

Yesterday's problem was about searching in a rotated array. Today's challenge was slightly different: What if we just needed to find the smallest number in that rotated array? 🚀 Day 76/365 — DSA Challenge Solved: Find Minimum in Rotated Sorted Array The Problem You're given a sorted array that has been rotated at some unknown pivot. 💡 My Approach This problem can be solved using Binary Search. Key observation: In a rotated sorted array, the smallest element is where the rotation happened. Steps: 1️⃣ Find the middle element 2️⃣ Compare it with the right element: nums[mid] > nums[right] 3️⃣ If true → the minimum must be in the right half 4️⃣ Otherwise → the minimum is in the left half (including mid) Complexity ⏱ Time: O(log n) 📦 Space: O(1) Day 76/365 complete. 💻 289 days to go. Code 👇 https://lnkd.in/dad5sZfu #DSA #Java #LeetCode #BinarySearch #Algorithms #LearningInPublic

𝐃𝐚𝐲 𝟐𝟗 – 𝐃𝐒𝐀 𝐉𝐨𝐮𝐫𝐧𝐞𝐲 | 𝐀𝐫𝐫𝐚𝐲𝐬 🚀 Today’s problem focused on applying binary search in a rotated sorted array with duplicates. 𝐏𝐫𝐨𝐛𝐥𝐞𝐦 𝐒𝐨𝐥𝐯𝐞𝐝 • Search in Rotated Sorted Array II 𝐀𝐩𝐩𝐫𝐨𝐚𝐜𝐡 • Used modified binary search • Calculated mid index in each iteration • Identified which half of the array was sorted • Narrowed the search range accordingly To handle duplicates: • If nums[left] == nums[mid] == nums[right], shrink the search space by moving both pointers. 𝐊𝐞𝐲 𝐋𝐞𝐚𝐫𝐧𝐢𝐧𝐠𝐬 • Rotated arrays require identifying the sorted half • Duplicate values can hide the sorted structure • Shrinking the search space helps handle ambiguous cases • Binary search logic often needs small adjustments for edge cases 𝐂𝐨𝐦𝐩𝐥𝐞𝐱𝐢𝐭𝐲 • Average Time: O(log n) • Worst Case Time: O(n) (due to duplicates) • Space: O(1) 𝐓𝐚𝐤𝐞𝐚𝐰𝐚𝐲 Binary search is not just about dividing the array — it's about understanding the structure of the data. 29 days consistent. On to Day 30 🚀 #DSA #Arrays #BinarySearch #LeetCode #Java #ProblemSolving #DailyCoding #LearningInPublic #SoftwareDeveloper

🔥 Day 349 – Daily DSA Challenge! 🔥 Problem: 🧱 Pyramid Transition Matrix You are stacking blocks to form a pyramid. Each block is represented by a letter. Given a bottom row and a list of allowed triples "ABC" meaning: A B → C Return true if you can build the pyramid to the top. 💡 Key Insight — Bitmask + DFS Instead of storing allowed transitions as lists, we encode them using bitmasks. For each pair (A, B) we store possible top blocks using a bitmask. Conceptually: Example: ABC ABD mask[A][B] = {C, D} stored as bits. 🧠 Recursive Construction We build the pyramid row by row: 1️⃣ Current row → cur 2️⃣ Generate next row → next 3️⃣ For each adjacent pair (cur[i], cur[i+1]) check all possible blocks above 4️⃣ Recursively continue until: length = 1 → pyramid complete ⚡ Optimization Trick To extract possible blocks from bitmask: bit = m & -m This isolates the lowest set bit, letting us iterate through candidates efficiently. ⚙️ Complexity Let n be bottom length. ✅ Time Complexity: ~ O(7ⁿ) worst-case (pruned heavily) ✅ Space Complexity: O(n) recursion stack But pruning via allowed transitions keeps it practical. 💬 Challenge for you 1️⃣ Why does using bitmasks make transitions faster than lists? 2️⃣ How would you add memoization to avoid recomputing rows? 3️⃣ Can you solve this using DP with states instead of DFS? #DSA #Day349 #LeetCode #DFS #Bitmask #Backtracking #Java #ProblemSolving #KeepCoding

🚀 Day 32 / 90 — DSA Challenge Today’s problem was a very interesting one: Split Array Largest Sum. At first glance, it looks like a typical array partitioning problem, but the real insight is recognizing that this problem can be solved efficiently using Binary Search on the Answer. 🔹 Problem Idea Given an array of integers and a value "k", the goal is to split the array into "k" subarrays such that the largest sum among those subarrays is minimized. Example: nums = [1,2,3,4,5], k = 2 Optimal split → "[1,2,3]" and "[4,5]" Largest sum = 9 🔹 Key Insight Instead of trying every possible split, we: 1️⃣ Use Binary Search on the possible maximum subarray sum 2️⃣ Check if we can split the array into "k" parts with that limit 3️⃣ Adjust the search range accordingly This reduces the complexity from an exponential brute force approach to an efficient O(n log(sum)) solution. 🔹 Concepts Practiced Today ✔ Binary Search on Answer ✔ Greedy partition checking ✔ Optimization problems with arrays ✔ Writing clean feasibility functions ("isPossible") 🔹 Takeaway Many array problems that ask to minimize the maximum value can often be solved using Binary Search on the Answer combined with a greedy validation function. Consistency is the real algorithm here. 32 days down, 58 more to go. #Day32 #90DaysOfDSA #DSAChallenge #LeetCode #BinarySearch #Java #ProblemSolving #SoftwareEngineering #CodingJourney Vignesh Reddy Julakanti

What if you had to find all anagrams of a word hidden inside another string? Not the words themselves... But the starting positions where they appear. 🚀 Day 69/365 — DSA Challenge Solved: Find All Anagrams in a String The problem: Given two strings: s -> the main string p -> the pattern Find all starting indices in s where an anagram of p appears. Example: s = "cbaebabacd" p = "abc" Output: [0, 6] Why? Index 0 -> "cba" -> anagram of "abc" Index 6 -> "bac" -> anagram of "abc" 💡 My Approach Step 1 Sort the characters of p. Example: abc -> abc Step 2 Slide through string s. At each position: • Take a substring of length p.length() • Sort its characters Step 3 Compare the sorted substring with the sorted pattern. If they match -> it's an anagram. Add the starting index to the result list. Example walkthrough: s = "abab" p = "ab" Substrings: ab -> match -> index 0 ba -> match -> index 1 ab -> match -> index 2 Output: [0,1,2] This problem reminded me: Anagrams often become easier to detect once the characters are sorted. Day 69/365 complete. Code 👇 https://lnkd.in/dad5sZfu #DSA #Java #LeetCode #LearningInPublic #ProblemSolving #Consistency