Binary Tree Preorder Traversal Algorithm

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

Day - 87 Binary Tree Level Order Traversal The problem - Given the root of a binary tree, return the level order traversal of its nodes' values (i.e., from left to right, level by level). Each level should be represented as a separate list. Brute Force - Use recursive DFS to traverse the tree while tracking depth. Store nodes at each depth level in separate lists. This gives O(n) time but requires complex depth tracking and is less intuitive than an iterative approach. Approach Used - •) Create res = new ArrayList<>(), queue = new ArrayDeque<>(). •) If root == null, return empty res. •) Add root to queue. •) While queue is not empty, 1 - Get current level size: size = queue.size(). 2 - Create list = new ArrayList<>(). 3 - While size > 0, - Poll node from queue, node = queue.poll(). - ⁠If node.left != null, add to queue: queue.add(node.left). - ⁠If node.right != null, add to queue: queue.add(node.right). - ⁠Add node value to current level: list.add(node.val). - ⁠Decrement size—. 4 - Add current level to result, res.add(list). •) Return res. Complexity - Time - O(n), where n = number of nodes. Space - O(w), where w = maximum width of tree. Note - Use BFS with a queue to traverse level by level. By capturing the queue size at the start of each iteration, we know exactly how many nodes belong to the current level. Process all nodes in that level, adding their children to the queue for the next level. This naturally groups nodes by level without needing depth tracking. #DSA #Java #SoftwareEngineering #InterviewPrep #LearnToCode #CodeDaily #ProblemSolving

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

Day 97/100 – LeetCode Challenge ✅ Problem: #105 Construct Binary Tree from Preorder and Inorder Traversal Difficulty: Medium Language: Java Approach: Recursive Construction with HashMap Lookup Time Complexity: O(n) Space Complexity: O(n) for map + recursion stack Key Insight: Preorder: [root, left subtree, right subtree] Inorder: [left subtree, root, right subtree] First element in preorder is always root Root's position in inorder splits left and right subtrees Solution Brief: Built HashMap to map inorder value → index for O(1) lookups. Maintained global index to track current root in preorder. Recursively built tree: Get root value from preorder at current index Find root position in inorder Build left subtree using elements before root Build right subtree using elements after root #LeetCode #Day97 #100DaysOfCode #Tree #BinaryTree #Java #Algorithm #CodingChallenge #ProblemSolving #ConstructBinaryTree #MediumProblem #Recursion #HashMap #DSA

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

🚀Day 98 of construct Binary search Tree from Preorder traversal. The Problem given an Array of Integers preorder, which represents the preorder traversal of BST (i.e., binary search Tree) construct the tree and return it's root guaranteed that there is always possible to find a binary tree with the given requirements for the given taste cases. Brute force - sort the preorder array to get inorder traversal, then use both preorder and inorder arrays to reconstruct the BST) ( like standard tree construction.) this gives O(n log n ) time due to sorting, which is inefficient when BST properties can guide direct construction. Approach used - •) if order. length ==0, return null ( empty tree). •) create root with first element, root = new tree node (Preorder [0]). •) return root. Helper function - insert Treenode root int val) •if val < root. val , insert in left subtree, - if root.left == null, create node , root left = new tree node( val). - Else recurse left , insert (root, left, val). •) Else ( when Val > root Val ), insert in right subtree, - if root. right == null, crate node , root right = new Tree node ( val ) - Else , recurse right , insert ( root. right, val ). complexity Time - O ( n × h ) , where h = height of tree is a number of nodes. Space - O( h), recursion stack depth. Note - preorder traversal's first element is always the root. By leveraging BST insertion rules . ( smaller values go left , larger go right ), we can sequentially insert each element from the preorder array. each insertion automatically finds the correct position building the BST without needing inorder traversal or sorting. #Java #LearnToCode #Problemsolving #DSA #coding

🚀 Day 38 of #100DaysOfCode Solved 154. Find Minimum in Rotated Sorted Array II on LeetCode 🔍 🧠 Key Insight: The array is sorted but rotated, and this version introduces duplicates, which makes the binary search logic slightly trickier. ⚙️ Approach: 🔹Use binary search with left and right pointers 🔹Compare nums[mid] with nums[right]: 🔹If nums[mid] > nums[right] → minimum lies in the right half 🔹If nums[mid] < nums[right] → minimum lies in the left half (including mid) 🔹If equal → safely shrink the search space by decrementing right This handles the ambiguity caused by duplicates. ⏱️ Time Complexity: Average: O(log n) Worst case: O(n) (when many duplicates exist) 📦 Space Complexity: O(1) #100DaysOfCode #LeetCode #DSA #BinarySearch #Arrays #Java #ProblemSolving #InterviewPrep #LearningInPublic

Day - 90 Binary Tree Maximum Path Sum The problem - Given the root of a binary tree, return the maximum path sum of any non-empty path. A path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root. The path sum is the sum of the node values in the path. Brute Force - For each node, consider all possible paths starting from that node using DFS, calculate their sums, and track the maximum. This gives O(n²) time complexity as we explore multiple paths from each node with redundant calculations. Approach Used - •) Declare res = {root.val}. •) Call helper function: dfs(root , res). •) Return res[0]. Helper Function - dfs( Treenode node , int[] res) •) If node == null, return 0 (no contribution from null node). •) leftSum = Math.max(0, dfs(node.left, res)), taking max with 0 to ignore negative paths. •) rightSum = Math.max(0, dfs(node.right, res)), taking max with 0 to ignore negative paths. •) Update maximum sum, res[0] = Math.max(res[0], leftSum + rightSum + node.val), this considers path through current node connecting both subtrees. •) Return Math.max(leftSum, rightSum) + node.val, parent can use only one branch left or right. Complexity - Time - O(n), where n = number of nodes. Space - O(h), where h = height of tree. Note - At each node, we consider two scenarios: (1) the maximum path passing through this node (connecting both subtrees), which updates the global maximum, and (2) the maximum path extending from this node to its parent (using only one subtree), which is returned. We use Math.max(0, childSum) to ignore negative contributions, as excluding negative paths yields better sums. #DSA #Java #SoftwareEngineering #InterviewPrep #LearnToCode #CodeDaily #ProblemSolving

Day 32 – Find Target Indices After Sorting Array Solved this problem by identifying the position of target elements after sorting without actually sorting the array. Key Learnings: Using counting technique instead of full sorting Reducing time complexity from O(n²) to O(n) Logical thinking based on sorted order properties #DSA #Java #Arrays #Optimization #CodingPractice #ProblemSolving