Insert Value into Binary Search Tree

Day - 103 Construct Binary Search Tree from Preorder Traversal The problem - Given an array of integers preorder, which represents the preorder traversal of a BST (i.e., binary search tree), construct the tree and return its root. It is guaranteed that there is always possible to find a binary search tree with the given requirements for the given test 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 preorder.length == 0, return null (empty tree). •) Create root with first element, root = new TreeNode(preorder[0]). •) For i = 1 to preorder.length - 1, insert each element, insert(root, preorder[i]). •) 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 TreeNode(val). - Else, recurse left, insert(root.left, val). •) Else (when val > root.val), insert in right subtree, - If root.right == null, create node, root.right = new TreeNode(val) - Else, recurse right, insert(root.right, val). Complexity - Time - O(n x h), where h = height of tree, n is 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. #DSA #Java #SoftwareEngineering #InterviewPrep #LearnToCode #CodeDaily #ProblemSolving

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

Yesterday's matrix problem was solved using traversal. Today's matrix problem was solved using Binary Search. Same topic. Different thinking. 🚀 Day 95/365 — DSA Challenge Solved: Search a 2D Matrix Key observation: The matrix is not just row-wise sorted. The first element of each row is greater than the last element of previous row. This means the matrix behaves like a sorted 1D array. So we can apply Binary Search. We convert index → row, col: row = mid / cols col = mid % cols And perform normal binary search. ⏱ Time: O(log(m * n)) 📦 Space: O(1) Day 95/365 complete. 💻 270 days to go. Code: https://lnkd.in/dad5sZfu #DSA #Java #LeetCode #BinarySearch #Matrix #LearningInPublic

🔥 Day 552 of #750DaysOfCode 🔥 🔐 LeetCode 2075: Decode the Slanted Ciphertext (Medium) Today’s problem looked tricky at first, but once the pattern clicked, it became super elegant 😄 🧠 Problem Understanding We are given an encoded string that was: Filled diagonally (↘) into a matrix Then read row-wise (→) 👉 Our task is to reverse this process and recover the original text. 💡 Key Insight If encoding is: ➡️ Fill diagonally ➡️ Read row-wise Then decoding is: ➡️ Read diagonally from row-wise string ⚙️ Approach ✅ Step 1: Calculate number of columns cols = encodedText.length() / rows; ✅ Step 2: Traverse diagonals starting from each column for (int startCol = 0; startCol < cols; startCol++) { int row = 0, col = startCol; while (row < rows && col < cols) { result.append(encodedText.charAt(row * cols + col)); row++; col++; } } ✅ Step 3: Remove trailing spaces 🚀 Complexity Time: O(n) Space: O(n) 🧠 What I Learned How to reverse matrix-based encoding patterns Converting 2D traversal → 1D index mapping Importance of pattern recognition in problems 📌 Takeaway Not every problem needs heavy logic. Sometimes, it's just about seeing the pattern correctly 👀 #LeetCode #DSA #Java #CodingJourney #ProblemSolving #Algorithms #SoftwareEngineering #100DaysOfCode #750DaysOfCode

Day 49/75 — Rearrange Array Elements by Sign Today’s problem focused on rearranging an array such that positive and negative numbers alternate, while preserving their original order. Approach: • Use two pointers (even index for positive, odd index for negative) • Traverse the array once • Place elements in correct positions directly Key logic: if (num >= 0) { result[posIdx] = num; posIdx += 2; } else { result[negIdx] = num; negIdx += 2; } Time Complexity: O(n) Space Complexity: O(n) A clean problem that reinforces index placement and pattern-based traversal. 49/75 🚀 #Day49 #DSA #Arrays #Java #Algorithms #LeetCode

𝐃𝐚𝐲 𝟓𝟔 – 𝐃𝐒𝐀 𝐉𝐨𝐮𝐫𝐧𝐞𝐲 | 𝐀𝐫𝐫𝐚𝐲𝐬 🚀 Today’s problem focused on finding a peak element using binary search. 𝐏𝐫𝐨𝐛𝐥𝐞𝐦 𝐒𝐨𝐥𝐯𝐞𝐝 • Find Peak Element 𝐀𝐩𝐩𝐫𝐨𝐚𝐜𝐡 • Used binary search instead of linear scan • Compared the middle element with its next element Logic: • If nums[mid] > nums[mid + 1] → peak lies on the left side (including mid) • Else → peak lies on the right side • Continued until left == right 𝐊𝐞𝐲 𝐋𝐞𝐚𝐫𝐧𝐢𝐧𝐠𝐬 • Binary search can be applied on patterns, not just sorted arrays • A peak always exists due to problem constraints • Comparing adjacent elements helps determine direction • Reducing the search space is the key idea 𝐂𝐨𝐦𝐩𝐥𝐞𝐱𝐢𝐭𝐲 • Time: O(log n) • Space: O(1) 𝐓𝐚𝐤𝐞𝐚𝐰𝐚𝐲 Binary search is not about sorted arrays — it’s about eliminating half of the search space using logic. 56 days consistent 🚀 On to Day 57. #DSA #Arrays #BinarySearch #LeetCode #Java #ProblemSolving #DailyCoding #LearningInPublic #SoftwareDeveloper

Day 91/100 – LeetCode Challenge ✅ Problem: #98 Validate Binary Search Tree Difficulty: Medium Language: Java Approach: Inorder Traversal with Stack Time Complexity: O(n) Space Complexity: O(h) where h = tree height Key Insight: Inorder traversal of BST produces sorted ascending sequence. Compare each visited node with previous node to detect violations. Solution Brief: Used stack for iterative inorder traversal. Maintained pre pointer to track previous visited node. While traversing: Push all left nodes to stack Pop node, check if root.val <= pre.val (violation) Update pre to current node Move to right subtree #LeetCode #Day91 #100DaysOfCode #Tree #BST #Java #Algorithm #CodingChallenge #ProblemSolving #ValidateBST #MediumProblem #InorderTraversal #Stack #DSA

Day 41/75 — Binary Tree Postorder Traversal Today’s problem was about performing postorder traversal of a binary tree. Traversal Order: • Left • Right • Root Approach: • Use recursion • Traverse left subtree • Traverse right subtree • Add current node value Key logic: postorder(root.left); postorder(root.right); res.add(root.val); Time Complexity: O(n) Space Complexity: O(h) (recursion stack, h = height of tree) Key Insight: Tree problems become much simpler when you clearly understand traversal orders. Postorder is especially useful when you need to process children before the parent. 41/75 🚀 #Day41 #DSA #BinaryTree #Recursion #Java #Algorithms #LeetCode

LeetCode 2130 — Maximum Twin Sum of a Linked List This problem gives the head of a linked list with even length. For a list of size n, the iᵗʰ node and the (n−1−i)ᵗʰ node are considered twin nodes. The twin sum is defined as the sum of the values of these two nodes. The task is to return the maximum twin sum in the linked list. Example : Input : 5 → 4 → 2 → 1 Twin pairs : (5,1) → sum = 6 (4,2) → sum = 6 Output : 6 Approach used — Reverse Second Half + Twin Traversal Because twin nodes lie symmetrically from the start and end, the list can be processed efficiently by reversing half of it. Two main steps are used during traversal. • First, fast and slow pointers are used to locate the middle of the linked list. - slow moves one step at a time. - fast moves two steps at a time. When fast reaches the end, slow will be positioned at the start of the second half. • The second half of the list is then reversed so that twin nodes align during traversal. After reversing : - One pointer starts from the beginning of the list. - Another pointer starts from the reversed second half. At each step : - The twin sum is calculated. - The maximum twin sum is updated. This approach works in O(n) time and O(1) extra space. #leetcode #datastructures #linkedlist #java #problemSolving