Search Blogs

Showing results for "Tree Traversal"

Found 23 results

LeetCode 145: Binary Tree Postorder Traversal – Java Recursive & Iterative Solution Explained

IntroductionLeetCode 145 – Binary Tree Postorder Traversal is one of the most important tree traversal problems for beginners learning Data Structures and Algorithms.This problem teaches:Binary Tree TraversalDepth First Search (DFS)RecursionStack-based traversalTree traversal patternsPostorder traversal is extremely useful in advanced tree problems such as:Tree deletionExpression tree evaluationBottom-up computationsDynamic programming on treesProblem Link🔗 https://leetcode.com/problems/binary-tree-postorder-traversal/Problem StatementGiven the root of a binary tree, return the postorder traversal of its nodes' values.What is Postorder Traversal?In postorder traversal, nodes are visited in this order:Left → Right → RootUnlike preorder or inorder traversal, the root node is processed at the end.ExampleInputroot = [1,null,2,3]Tree Structure:1\2/3Postorder TraversalTraversal order:3 → 2 → 1Output:[3,2,1]Recursive Approach (Most Common)IntuitionIn postorder traversal:Traverse left subtreeTraverse right subtreeVisit current nodeThis naturally fits recursion because trees themselves are recursive structures.Recursive DFS VisualizationTraversal pattern:Left → Right → RootRecursive function:postorder(node.left)postorder(node.right)visit(node)Java Recursive Solution/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* }*/class Solution {public void solve(List<Integer> list, TreeNode root) {if(root == null) return;solve(list, root.left);solve(list, root.right);list.add(root.val);}public List<Integer> postorderTraversal(TreeNode root) {List<Integer> list = new ArrayList<>();solve(list, root);return list;}}Dry Run – Recursive ApproachTree:1\2/3Step 1Start at:1Move left:nullReturn back.Step 2Move right to:2Move left to:3Left and right of 3 are null.Add:3Step 3Return to:2Add:2Step 4Return to:1Add:1Final Answer[3,2,1]Time Complexity – RecursiveTime ComplexityO(N)Every node is visited once.Space ComplexityO(H)Where:H = height of the treeRecursive call stack uses extra spaceWorst case:O(N)for skewed trees.Iterative Approach (Interview Follow-Up)The follow-up asks:Can you solve it iteratively?Yes.We use stacks to simulate recursion.Iterative Postorder IntuitionPostorder traversal order is:Left → Right → RootOne common trick is:Traverse in modified preorder:Root → Right → LeftReverse the result.After reversing, we get:Left → Right → Rootwhich is postorder traversal.Stack-Based Iterative LogicAlgorithmPush root into stack.Pop node.Add node value to answer.Push left child.Push right child.Reverse final answer.Java Iterative Solutionclass Solution {public List<Integer> postorderTraversal(TreeNode root) {LinkedList<Integer> ans = new LinkedList<>();if(root == null) return ans;Stack<TreeNode> stack = new Stack<>();stack.push(root);while(!stack.isEmpty()) {TreeNode node = stack.pop();ans.addFirst(node.val);if(node.left != null) {stack.push(node.left);}if(node.right != null) {stack.push(node.right);}}return ans;}}Dry Run – Iterative ApproachTree:1\2/3Step 1Push:1Step 2Pop:1Add at front:[1]Push right child:2Step 3Pop:2Add at front:[2,1]Push left child:3Step 4Pop:3Add at front:[3,2,1]Final Answer[3,2,1]Comparison of ApproachesApproachAdvantagesDisadvantagesRecursiveEasy to understandUses recursion stackIterativeBetter interview practiceSlightly harder logicInterview ExplanationIn interviews, explain:Postorder traversal processes nodes in Left → Right → Root order. Recursion naturally handles this traversal. Iteratively, we simulate recursion using a stack and reverse traversal order.This demonstrates strong tree traversal understanding.Common Mistakes1. Wrong Traversal OrderIncorrect:Root → Left → RightThat is preorder traversal.Correct postorder:Left → Right → Root2. Forgetting Null Base CaseAlways check:if(root == null) return;3. Incorrect Stack Push OrderFor iterative solution:Push left firstPush right secondbecause we reverse the result later.FAQsQ1. Why is postorder traversal useful?It is used in:Tree deletionExpression tree evaluationBottom-up dynamic programmingCalculating subtree informationQ2. Which approach is preferred in interviews?Recursive is simpler.Iterative is often asked as a follow-up.Q3. Can postorder traversal be done without stack or recursion?Yes.Using Morris Traversal.Q4. What is the difference between preorder, inorder, and postorder?TraversalOrderPreorderRoot → Left → RightInorderLeft → Root → RightPostorderLeft → Right → RootBonus: Morris Postorder TraversalMorris traversal performs tree traversal using:O(1)extra space.This is considered an advanced interview topic.ConclusionLeetCode 145 is an excellent beginner-friendly tree traversal problem.It teaches:DFS traversalRecursionStack simulationBinary tree fundamentalsThe key postorder pattern is:Left → Right → RootMastering this traversal helps in solving many advanced tree problems such as:Tree DPTree deletionExpression evaluationSubtree calculationsAdvanced DFS problems

LeetCodeBinary Tree Postorder TraversalBinary TreeTree TraversalJavaDFSStackRecursionEasy

LeetCode 144: Binary Tree Preorder Traversal – Java Recursive & Iterative Solution Explained

IntroductionLeetCode 144 – Binary Tree Preorder Traversal is one of the most important beginner-friendly tree traversal problems in Data Structures and Algorithms.This problem helps you understand:Binary Tree TraversalDepth First Search (DFS)RecursionStack-based traversalTree traversal patternsPreorder traversal is widely used in:Tree copyingSerializationExpression treesDFS-based problemsHierarchical data processingIt is also one of the most commonly asked tree problems in coding interviews.Problem Link🔗 ProblemLeetCode 144: Binary Tree Preorder TraversalOfficial Problem:LeetCode Problem LinkProblem StatementGiven the root of a binary tree, return the preorder traversal of its nodes' values.What is Preorder Traversal?In preorder traversal, nodes are visited in this order:Root → Left → RightThe root node is processed first before traversing subtrees.ExampleInputroot = [1,null,2,3]Tree Structure:1\2/3Preorder TraversalTraversal order:1 → 2 → 3Output:[1,2,3]Recursive Approach (Most Common)IntuitionIn preorder traversal:Visit current nodeTraverse left subtreeTraverse right subtreeThis naturally fits recursion because trees themselves are recursive structures.Recursive DFS VisualizationTraversal pattern:Root → Left → RightRecursive function:visit(node)preorder(node.left)preorder(node.right)Java Recursive Solution/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* }*/class Solution {public void solve(List<Integer> list, TreeNode root) {if(root == null) return;list.add(root.val);solve(list, root.left);solve(list, root.right);}public List<Integer> preorderTraversal(TreeNode root) {List<Integer> list = new ArrayList<>();solve(list, root);return list;}}Dry Run – Recursive ApproachTree:1\2/3Step 1Start at:1Add:1Move right to:2Step 2Add:2Move left to:3Step 3Add:3Final Answer[1,2,3]Time Complexity – RecursiveTime ComplexityO(N)Every node is visited once.Space ComplexityO(H)Where:H = height of treeRecursive call stack uses extra spaceWorst case:O(N)for skewed trees.Iterative Approach (Interview Follow-Up)The follow-up asks:Can you solve it iteratively?Yes.We use a stack to simulate recursion.Iterative Preorder IntuitionPreorder traversal order is:Root → Left → RightUsing a stack:Process current node immediatelyPush right child firstPush left child secondWhy?Because stacks follow:Last In First Out (LIFO)So left subtree gets processed first.Stack-Based Iterative LogicAlgorithmPush root into stack.Pop node.Add node value.Push right child.Push left child.Repeat until stack becomes empty.Java Iterative Solutionclass Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> ans = new ArrayList<>();if(root == null) return ans;Stack<TreeNode> stack = new Stack<>();stack.push(root);while(!stack.isEmpty()) {TreeNode node = stack.pop();ans.add(node.val);if(node.right != null) {stack.push(node.right);}if(node.left != null) {stack.push(node.left);}}return ans;}}Dry Run – Iterative ApproachTree:1\2/3Step 1Push:1Step 2Pop:1Add:[1]Push right child:2Step 3Pop:2Add:[1,2]Push left child:3Step 4Pop:3Add:[1,2,3]Final Answer[1,2,3]Comparison of ApproachesApproachAdvantagesDisadvantagesRecursiveEasy to understandUses recursion stackIterativeBetter interview practiceSlightly harder logicInterview ExplanationIn interviews, explain:Preorder traversal processes nodes in Root → Left → Right order. Recursion naturally handles this traversal. Iteratively, we use a stack and push the right child before the left child so the left subtree gets processed first.This demonstrates strong DFS and stack understanding.Common Mistakes1. Wrong Traversal OrderIncorrect:Left → Root → RightThat is inorder traversal.Correct preorder:Root → Left → Right2. Forgetting Null Base CaseAlways check:if(root == null) return;3. Wrong Stack Push OrderFor iterative traversal:Push right firstPush left secondOtherwise traversal order becomes incorrect.FAQsQ1. Why is preorder traversal useful?It is heavily used in:Tree cloningSerializationDFS traversalExpression treesQ2. Which approach is preferred in interviews?Recursive is simpler.Iterative is often asked as a follow-up.Q3. Can preorder traversal be done without stack or recursion?Yes.Using Morris Traversal.Q4. What is the difference between preorder, inorder, and postorder?TraversalOrderPreorderRoot → Left → RightInorderLeft → Root → RightPostorderLeft → Right → RootBonus: Morris Preorder TraversalMorris traversal performs preorder traversal using:O(1)extra space.This is considered an advanced interview topic.ConclusionLeetCode 144 is one of the most fundamental binary tree traversal problems.It teaches:DFS traversalRecursionStack simulationBinary tree fundamentalsThe key preorder pattern is:Root → Left → RightMastering this traversal builds a strong foundation for advanced tree problems such as:Tree serializationDFS-based problemsTree reconstructionExpression treesMorris traversal

LeetCodeBinary Tree Preorder TraversalBinary TreeTree TraversalJavaDFSStackRecursionEasy

LeetCode 102: Binary Tree Level Order Traversal – Java BFS Solution Explained

IntroductionLeetCode 102 – Binary Tree Level Order Traversal is one of the most important Binary Tree traversal problems for coding interviews.This problem introduces:Breadth First Search (BFS)Queue data structureLevel-by-level traversalTree traversal patternsInterview-level BFS thinkingUnlike DFS traversals like preorder, inorder, and postorder, this problem explores the tree level by level.This traversal is widely used in:Graph traversalShortest path problemsTree serializationZigzag traversalBFS-based interview questionsProblem Link🔗 https://leetcode.com/problems/binary-tree-level-order-traversal/Problem StatementGiven the root of a binary tree, return the level order traversal of its nodes' values.Traversal should happen:Level by levelLeft to rightExampleInputroot = [3,9,20,null,null,15,7]Tree Structure: 3 / \ 9 20 / \ 15 7Level Order TraversalLevel 1:[3]Level 2:[9,20]Level 3:[15,7]Final Output:[[3],[9,20],[15,7]]Understanding the ProblemThe main challenge is:Process nodes level by level.This is exactly what:Breadth First Search (BFS)is designed for.Why Queue is Used?A queue follows:First In First Out (FIFO)This ensures:Nodes are processed in insertion orderParent nodes are processed before child nodesLevels are traversed correctlyBrute Force IntuitionOne brute force idea is:Calculate height of treeTraverse each level separatelyStore nodes level by levelBrute Force ComplexityThis approach becomes inefficient because:Each level traversal may revisit nodesComplexity may become:O(N²)for skewed trees.Optimal BFS IntuitionInstead of traversing each level separately:Use a queueProcess nodes level by level naturallyAt every level:Store queue sizeProcess exactly those many nodesAdd children into queueMove to next levelKey BFS ObservationBefore processing a level:int size = queue.size();This tells us:How many nodes belong to the current level.BFS AlgorithmSteps1. Initialize QueueInsert root node.2. Process Until Queue Becomes EmptyWhile queue is not empty:Find current level sizeTraverse current levelStore valuesPush child nodes3. Store Current LevelAfter processing one level:ans.add(levelList);Java BFS Solution/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * } */class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> ans = new ArrayList<>(); Queue<TreeNode> queue = new LinkedList<>(); if(root == null) return ans; queue.offer(root); while(!queue.isEmpty()) { int size = queue.size(); List<Integer> level = new ArrayList<>(); for(int i = 0; i < size; i++) { root = queue.poll(); level.add(root.val); if(root.left != null) queue.offer(root.left); if(root.right != null) queue.offer(root.right); } ans.add(level); } return ans; }}Dry RunInputroot = [3,9,20,null,null,15,7]Tree: 3 / \ 9 20 / \ 15 7Initial Queue[3]Level 1Queue size:1Process:3Add children:9, 20Level result:[3]Queue now:[9,20]Level 2Queue size:2Process:9, 20Add children:15, 7Level result:[9,20]Queue now:[15,7]Level 3Queue size:2Process:15, 7Level result:[15,7]Queue becomes empty.Final Answer[[3],[9,20],[15,7]]Time Complexity AnalysisTime ComplexityO(N)Every node is visited exactly once.Space ComplexityO(N)Queue may store an entire level of nodes.DFS Alternative ApproachThis problem can also be solved using DFS recursion.Idea:Pass current level during recursionCreate new list when level appears first timeAdd node into correct level listJava DFS Solutionclass Solution { public void dfs(TreeNode root, int level, List<List<Integer>> ans) { if(root == null) return; if(level == ans.size()) { ans.add(new ArrayList<>()); } ans.get(level).add(root.val); dfs(root.left, level + 1, ans); dfs(root.right, level + 1, ans); } public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> ans = new ArrayList<>(); dfs(root, 0, ans); return ans; }}BFS vs DFS for Level Order TraversalApproachAdvantagesDisadvantagesBFSNatural level traversalUses queueDFSRecursive solutionSlightly harder intuitionInterview ExplanationIn interviews, explain:Level order traversal is a BFS problem because we process nodes level by level. A queue naturally supports this traversal order.This demonstrates strong BFS understanding.Common Mistakes1. Forgetting Queue SizeWithout storing:int size = queue.size();levels cannot be separated correctly.2. Using DFS IncorrectlySimple DFS alone does not guarantee level ordering.3. Forgetting Null CheckAlways handle:if(root == null)FAQsQ1. Why is BFS preferred here?Because BFS naturally processes nodes level by level.Q2. Can this problem be solved recursively?Yes.Using DFS with level tracking.Q3. What data structure is mainly used?Queue.Q4. Is Level Order Traversal important?Yes.It is one of the most frequently asked BFS tree problems.Related ProblemsAfter mastering this problem, practice:Binary Tree Zigzag Level Order TraversalAverage of Levels in Binary TreeRight Side View of Binary TreeBinary Tree Vertical Order TraversalMaximum Depth of Binary TreeConclusionLeetCode 102 is one of the most important BFS tree traversal problems.It teaches:BFS traversalQueue usageLevel-by-level processingTree traversal fundamentalsThe key idea is:Use queue size to separate levels.Once this intuition becomes clear, many BFS-based tree interview problems become much easier.

LeetCodeBinary Tree Level Order TraversalBFSQueueBinary TreeJavaTree TraversalMedium

LeetCode 94: Binary Tree Inorder Traversal – Java Recursive & Iterative Solution Explained

IntroductionLeetCode 94 – Binary Tree Inorder Traversal is one of the most important beginner-friendly tree problems in Data Structures and Algorithms.This problem helps you understand:Binary tree traversalDepth First Search (DFS)RecursionStack-based traversalTree interview fundamentalsIt is commonly asked in coding interviews because tree traversal forms the foundation of many advanced tree problems.Problem Link🔗 ProblemLeetCode 94: Binary Tree Inorder TraversalOfficial Problem:LeetCode Problem LinkProblem StatementGiven the root of a binary tree, return the inorder traversal of its nodes' values.What is Inorder Traversal?In inorder traversal, we visit nodes in this order:Left → Root → RightExampleInputroot = [1,null,2,3]Tree Structure:1\2/3Inorder TraversalStep-by-step:1 → 3 → 2Output:[1,3,2]Recursive Approach (Most Common)IntuitionIn inorder traversal:Traverse left subtreeVisit current nodeTraverse right subtreeThis naturally fits recursion because trees themselves are recursive structures.Recursive DFS VisualizationTraversal order:Left → Node → RightRecursive function:inorder(node.left)visit(node)inorder(node.right)Java Recursive Solution/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* }*/class Solution {public void solve(List<Integer> list, TreeNode root) {if(root == null) return;solve(list, root.left);list.add(root.val);solve(list, root.right);}public List<Integer> inorderTraversal(TreeNode root) {List<Integer> list = new ArrayList<>();solve(list, root);return list;}}Dry Run – Recursive ApproachTree:1\2/3Step 1Start at:1Move left:nullReturn back.Add:1Step 2Move right to:2Move left to:3Add:3Return back.Add:2Final Answer[1,3,2]Time Complexity – RecursiveTime ComplexityO(N)Every node is visited once.Space ComplexityO(H)Where:H = height of treeRecursive call stack uses extra spaceWorst case:O(N)for skewed trees.Iterative Approach (Interview Follow-Up)The follow-up asks:Can you solve it iteratively?Yes.We use a stack to simulate recursion.Iterative Inorder IntuitionThe recursive order is:Left → Node → RightSo iteratively:Keep pushing left nodes into stackProcess current nodeMove to right subtreeStack-Based Traversal LogicAlgorithmWhile current node exists OR stack is not empty:Push all left nodesPop top nodeAdd node valueMove to right subtreeJava Iterative Solutionclass Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> ans = new ArrayList<>();Stack<TreeNode> stack = new Stack<>();TreeNode curr = root;while(curr != null || !stack.isEmpty()) {while(curr != null) {stack.push(curr);curr = curr.left;}curr = stack.pop();ans.add(curr.val);curr = curr.right;}return ans;}}Dry Run – Iterative ApproachTree:1\2/3Step 1Push:1Stack:[1]Step 2Pop:1Add:1Move right to:2Step 3Push:23Stack:[2,3]Step 4Pop:3Add:3Step 5Pop:2Add:2Final Answer[1,3,2]Comparison of ApproachesApproachAdvantagesDisadvantagesRecursiveEasy to write and understandUses recursion stackIterativeBetter interview practiceSlightly harder logicInterview ExplanationIn interviews, explain:In inorder traversal, we process nodes in Left → Root → Right order. Recursion naturally fits this traversal. For iterative traversal, we use a stack to simulate recursive calls.This demonstrates strong tree traversal understanding.Common Mistakes1. Wrong Traversal OrderIncorrect:Root → Left → RightThat is preorder traversal.Correct inorder:Left → Root → Right2. Forgetting Null Base CaseAlways check:if(root == null) return;3. Stack Handling ErrorsIn iterative traversal:Push all left nodes firstThen process nodeThen move rightFAQsQ1. Why is inorder traversal important?It is heavily used in:Binary Search TreesExpression treesTree reconstruction problemsQ2. What is the inorder traversal of a BST?It produces values in sorted order.Q3. Which approach is better for interviews?Recursive is easier.Iterative is preferred for deeper interview rounds.Q4. Can inorder traversal be done without stack or recursion?Yes.Using Morris Traversal with:O(1)space.Bonus: Morris Traversal (Advanced)Morris Traversal performs inorder traversal without recursion or stack.ComplexityTime ComplexityO(N)Space ComplexityO(1)This is an advanced interview optimization.ConclusionLeetCode 94 is one of the most fundamental tree traversal problems.It teaches:DFS traversalRecursionStack simulationBinary tree fundamentalsThe key inorder pattern is:Left → Root → RightMastering this problem builds a strong foundation for advanced tree interview questions like:BST validationTree iteratorsTree reconstructionMorris traversalKth smallest in BST

LeetCodeBinary Tree Inorder TraversalBinary TreeTree TraversalJavaDFSStackRecursionEasy

LeetCode 230: Kth Smallest Element in a BST – Java Recursive Inorder Traversal Solution

IntroductionLeetCode 230 – Kth Smallest Element in a BST is one of the most important Binary Search Tree interview problems.This question is popular because it tests:BST propertiesInorder traversalDFS recursionTree traversal optimizationRecursive state managementUnderstanding this problem properly builds a strong foundation for advanced BST problems.Problem Link🔗 https://leetcode.com/problems/kth-smallest-element-in-a-bst/Problem StatementGiven:Root of a Binary Search TreeInteger kReturn:The kth smallest value in the BSTThe indexing is:1-indexedExample 1Inputroot = [3,1,4,null,2]k = 1Output1ExplanationBST inorder traversal becomes:[1,2,3,4]1st smallest element is:1Example 2Inputroot = [5,3,6,2,4,null,null,1]k = 3Output3Key ObservationThe most important BST property:Inorder Traversal of BST gives sorted orderExample:5/ \3 6/ \2 4/1Inorder traversal:1 → 2 → 3 → 4 → 5 → 6So:kth smallest = kth node in inorder traversalIntuitionWe perform:Left → Root → RightWhile traversing:Keep counting visited nodesWhen count becomes kStore answerNo need to traverse entire tree after finding answer.Brute Force ApproachIdeaStore complete inorder traversal in listReturn:list.get(k - 1)Brute Force Java Solutionclass Solution {public void inorder(TreeNode root, List<Integer> list) {if(root == null) return;inorder(root.left, list);list.add(root.val);inorder(root.right, list);}public int kthSmallest(TreeNode root, int k) {List<Integer> list = new ArrayList<>();inorder(root, list);return list.get(k - 1);}}Complexity of Brute ForceTime ComplexityO(N)Space ComplexityO(N)Extra list storage required.Optimized Recursive ApproachIdeaInstead of storing entire traversal:Maintain counterStop when kth node is reachedThis saves unnecessary storage.Java Solutionclass Solution {int coun = 0;int ans = -1;public void inorder(TreeNode root, int k, List<Integer> lis) {if(root == null) return;inorder(root.left, k, lis);coun++;if(coun == k) {ans = root.val;return;}inorder(root.right, k, lis);}public int kthSmallest(TreeNode root, int k) {List<Integer> lis = new ArrayList<>();inorder(root, k, lis);return ans;}}Cleaner Optimized Versionclass Solution {int count = 0;int answer = -1;public void inorder(TreeNode root, int k) {if(root == null) return;inorder(root.left, k);count++;if(count == k) {answer = root.val;return;}inorder(root.right, k);}public int kthSmallest(TreeNode root, int k) {inorder(root, k);return answer;}}Why This WorksBST inorder traversal always visits nodes in:sorted ascending orderSo:1st visited node = smallest2nd visited node = second smallestkth visited node = kth smallestDry RunInputroot = [5,3,6,2,4,null,null,1]k = 3BST Structure5/ \3 6/ \2 4/1Inorder Traversal1 → 2 → 3 → 4 → 5 → 6Counter ProgressNodeCount112233At count = 3:answer = 3Final Output3Iterative Stack ApproachIdeaUse explicit stack instead of recursion.Iterative Java Solutionclass Solution {public int kthSmallest(TreeNode root, int k) {Stack<TreeNode> stack = new Stack<>();while(true) {while(root != null) {stack.push(root);root = root.left;}root = stack.pop();k--;if(k == 0) {return root.val;}root = root.right;}}}Time Complexity AnalysisOptimized RecursiveTime ComplexityO(H + k)Where:H = tree heightWe visit only required nodesWorst case:O(N)Space ComplexityO(H)Recursive stack space.Iterative ComplexityTime ComplexityO(H + k)Space ComplexityO(H)Stack space.Follow-Up OptimizationProblem Follow-UpWhat if BST changes frequently?Example:Insert operationsDelete operationsFrequent kth smallest queriesAdvanced OptimizationStore:size of subtreeinside every node.This allows:O(log N)kth smallest queries.This concept is used in:Order Statistic TreesAugmented BSTsIndexed TreesInterview ExplanationIn interviews, explain:Inorder traversal of a BST gives nodes in sorted order. Therefore, the kth visited node during inorder traversal is the kth smallest element.This demonstrates:BST understandingDFS recursionTree traversal masteryOptimization thinkingCommon Mistakes1. Forgetting BST PropertyThis solution works because BST inorder traversal is sorted.Not true for normal binary trees.2. Using Extra Array UnnecessarilyOptimized approach avoids storing entire traversal.3. Incorrect Counter PlacementCounter must increase:AFTER left traversalBEFORE right traversal4. Forgetting Early ReturnOnce kth element is found:answer should be stored immediatelyFAQsQ1. Why does inorder traversal work?Because BST inorder traversal produces sorted order.Q2. Can this be solved iteratively?Yes.Using stack-based inorder traversal.Q3. Why is BST important here?Without BST ordering property:kth smallest cannot be determined using inorderQ4. Is this frequently asked?Yes.It is one of the most common BST interview questions.ConclusionLeetCode 230 is an excellent BST problem for mastering:Inorder traversalBST propertiesDFS recursionStack traversalTree optimizationThe core insight is:Inorder traversal of a BST always produces sorted order.Once this concept becomes intuitive, many BST interview problems become much easier.

LeetCodeKth Smallest Element in BSTBinary Search TreeJavaInorder TraversalBSTMedium

LeetCode 104: Maximum Depth of Binary Tree – Java Recursive Solution Explained

IntroductionLeetCode 104 – Maximum Depth of Binary Tree is one of the most important beginner tree problems in Data Structures and Algorithms.This problem teaches:Binary Tree TraversalDepth First Search (DFS)RecursionTree Height CalculationDivide and ConquerIt is one of the most frequently asked tree questions in coding interviews because it builds the foundation for:Tree recursionHeight problemsBalanced tree problemsDiameter problemsDFS traversalIf you are starting binary trees, this is one of the best problems to master first.Problem Link🔗 https://leetcode.com/problems/maximum-depth-of-binary-tree/Problem StatementGiven the root of a binary tree:Return:Maximum depth of the treeMaximum depth means:Number of nodes along the longest path from root to the farthest leaf node.Example 1Inputroot = [3,9,20,null,null,15,7]Tree: 3 / \ 9 20 / \ 15 7Output3Explanation:Longest path:3 → 20 → 15contains:3 nodesExample 2Inputroot = [1,null,2]Tree:1 \ 2Output:2Understanding Maximum DepthDepth means:How many levels exist in the treeFor example: 1 / \ 2 3 / 4Levels:Level 1 → 1Level 2 → 2,3Level 3 → 4Maximum depth:3Key ObservationThe depth of a tree depends on:Maximum depth of left subtreeandMaximum depth of right subtreeSo:Depth(root)=1 + max(leftDepth, rightDepth)This is the core recursive formula.Recursive IntuitionAt every node:Find depth of left subtreeFind depth of right subtreeTake maximumAdd current nodeThis naturally becomes a recursive DFS problem.Java Recursive Solutionclass Solution { public int maxDepth(TreeNode root) { if(root == null) return 0; int left = maxDepth(root.left); int right = maxDepth(root.right); return 1 + Math.max(left, right); }}Why This WorksAt every node:Recursively calculate left depthRecursively calculate right depthChoose bigger depthAdd:1for current node.This continues until leaf nodes.Dry RunInput 3 / \ 9 20 / \ 15 7Step 1Start from root:3Step 2Left subtree:9Depth:1Step 3Right subtree:20Its children:15 and 7Depth becomes:2Step 4At root:1 + max(1,2)Result:3Recursive Call FlowmaxDepth(3) ├── maxDepth(9) │ ├── 0 │ └── 0 │ └── maxDepth(20) ├── maxDepth(15) └── maxDepth(7)Then values return upward.Alternative BFS ApproachWe can also solve this using:Level Order Traversalusing a queue.Every level increases depth by:1BFS Java Solutionclass Solution { public int maxDepth(TreeNode root) { if(root == null) return 0; Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); int depth = 0; while(!queue.isEmpty()) { int size = queue.size(); for(int i = 0; i < size; i++) { TreeNode node = queue.poll(); if(node.left != null) queue.offer(node.left); if(node.right != null) queue.offer(node.right); } depth++; } return depth; }}DFS vs BFSApproachTechniqueSpaceDFSRecursionO(H)BFSQueueO(N)Time Complexity AnalysisRecursive DFS SolutionTime ComplexityO(N)because every node is visited once.Space ComplexityO(H)where:H = tree heightWorst case:O(N)for skewed tree.BFS SolutionTime ComplexityO(N)Space ComplexityO(N)queue may contain full level.Interview ExplanationIn interviews, explain:The depth of a node depends on the maximum depth between its left and right subtree. This naturally forms a recursive divide-and-conquer problem.This demonstrates:Tree recursion understandingDFS traversal knowledgeDivide and conquer thinkingCommon Mistakes1. Forgetting Base CaseAlways handle:if(root == null) return 0;2. Using Min Instead of MaxWe need:Longest pathnot shortest.3. Incorrect Depth CountingRemember to add:1for current node.FAQsQ1. What is maximum depth?It is the number of nodes in the longest root-to-leaf path.Q2. Why is recursion preferred?Tree problems naturally fit recursive structures.Q3. Can this be solved iteratively?Yes.Using BFS with queue.Q4. Is this problem important for interviews?Very important.It is one of the most fundamental tree recursion problems.Related ProblemsAfter mastering this problem, practice:Minimum Depth of Binary TreeBalanced Binary TreeDiameter of Binary TreeBinary Tree Level Order TraversalPath SumConclusionLeetCode 104 is one of the most important beginner binary tree problems.It teaches:Recursive DFSTree height calculationDivide and conquerBinary tree traversalThe key insight is:Maximum depth equals 1 + maximum depth of left and right subtree.Once this recursive pattern becomes clear, many advanced tree problems become easier to solve.

LeetCodeDepth of Binary TreeJavaBinary TreeDFSBFSRecursionTreeEasy

Inorder Successor in BST – Java Optimized BST Solution with Dry Run

IntroductionThe Inorder Successor in BST problem is one of the most important Binary Search Tree interview questions asked in coding interviews and online coding platforms like GeeksforGeeks.This problem tests your understanding of:Binary Search Tree propertiesInorder traversalRecursive searchingTree optimization techniquesSuccessor logic in BSTUnderstanding this problem properly helps in solving many advanced BST questions efficiently.Problem Link🔗 GeeksforGeeks – Inorder Successor in BSTProblem StatementGiven:A Binary Search TreeA reference node kFind the:Inorder Successorof that node.What is Inorder Successor?The inorder successor of a node is:The next greater node in the inorder traversal of the BST.Example 1Inputroot = [2,1,3]k = 2Inorder Traversal1 2 3Output3Example 2Inputroot = [20,8,22,4,12,null,null,null,null,10,14]k = 8Inorder Traversal4 8 10 12 14 20 22Output10Key BST ObservationIn a BST:Left subtree -> smaller valuesRight subtree -> greater valuesThe inorder traversal of BST is always:Sorted orderThis property helps us optimize the search.IntuitionSuppose:k = 8and current node is:20Since:20 > 8this node can potentially be the inorder successor.But there may exist a smaller valid successor in the left subtree.So:Store current node as possible answerMove leftBrute Force ApproachIdeaPerform inorder traversalStore traversal in listFind node kReturn next elementBrute Force Java Solutionclass Solution { List<Integer> inorder = new ArrayList<>(); void traverse(Node root) { if(root == null) return; traverse(root.left); inorder.add(root.data); traverse(root.right); } public int inOrderSuccessor(Node root, Node k) { traverse(root); for(int i = 0; i < inorder.size() - 1; i++) { if(inorder.get(i) == k.data) { return inorder.get(i + 1); } } return -1; }}Brute Force ComplexityTime ComplexityO(N)Space ComplexityO(N)because of traversal list.Optimized BST ApproachInstead of traversing the entire tree:Use BST propertiesReduce unnecessary traversalSearch efficientlyOptimized Java Solutionclass Solution { int c = -1; int solve(Node root, Node x, int c) { if(root == null) return c; if(root.data > x.data) { c = root.data; return solve(root.left, x, c); } else { return solve(root.right, x, c); } } public int inOrderSuccessor(Node root, Node k) { return solve(root, k, c); }}How This Solution WorksWhenever:root.data > k.datathe current node becomes a possible successor candidate.But there may exist a smaller valid successor in the left subtree.So:Store current nodeMove leftWhy Move Right Otherwise?If:root.data <= k.datathen current node cannot be successor.Move right to search for larger values.Dry RunInput 20 / \ 8 22 / \ 4 12 / \ 10 14k = 8Step 1Current node:20Since:20 > 8possible successor:20Move left.Step 2Current node:8Since:8 <= 8Move right.Step 3Current node:12Since:12 > 8update successor:12Move left.Step 4Current node:10Since:10 > 8update successor:10Move left.Step 5Node becomes null.Return:10Final Answer10Alternative Inorder Traversal ApproachAnother common approach:Perform inorder traversalTrack previous nodeWhen previous node becomes k, current node is successorAlternative Recursive Solutionclass Solution { Node prev = null; Node succ = null; void solve(Node root, Node k) { if(root == null || succ != null) return; solve(root.left, k); if(prev != null && prev.data == k.data) { succ = root; } prev = root; solve(root.right, k); } public int inOrderSuccessor(Node root, Node k) { solve(root, k); return succ != null ? succ.data : -1; }}Time Complexity AnalysisOptimized BST SolutionBest CaseO(log N)Balanced BST.Worst CaseO(N)Skewed BST.Space ComplexityRecursive StackO(H)where:H = height of treeInterview ExplanationIn interviews explain:Whenever we encounter a node greater than k, it becomes a possible inorder successor candidate. Then we move left to search for a smaller valid successor.This demonstrates:BST optimization understandingRecursive traversal logicEfficient searching skillsCommon Mistakes1. Traversing Entire Tree UnnecessarilyBST property already reduces search space.2. Returning First Greater NodeNeed the:smallest greater nodenot any greater node.3. Forgetting Candidate UpdateAlways update candidate before moving left.4. Confusing Floor/Ceil LogicSuccessor logic is different from:FloorCeilPredecessorFAQsQ1. What is inorder successor?The next greater node in inorder traversal.Q2. Why BST helps optimization?BST ordering allows skipping unnecessary branches.Q3. Can inorder successor be absent?Yes.If node is largest element, answer is:-1Q4. Can this be solved iteratively?Yes.Iterative solution is also common in interviews.Related BST ProblemsPractice these next:Search in BSTCeil in BSTFloor in BSTValidate BSTLowest Common Ancestor in BSTKth Smallest Element in BSTConclusionInorder Successor in BST is a very important interview problem because it teaches:BST optimizationRecursive searchingSuccessor logicTree traversal efficiencyThe key idea is:Whenever a node is greater than k, it becomes a possible successor candidate, but a smaller valid successor may still exist in the left subtree.Mastering this logic makes advanced BST problems significantly easier.

BSTGFGTreeBinary Search TreeJavaTree TraversalRecursionEasy

Queue Data Structure Complete Guide - Java Explained With All Operations

IntroductionIf you have been learning Data Structures and Algorithms, you have probably already spent time with arrays, linked lists, and stacks. Now it is time to meet one of the most important and widely used data structures in computer science — the Queue.Queue is not just a theoretical concept. It powers some of the most critical systems you use every day — from how your printer handles jobs, to how your CPU schedules tasks, to how Google Maps finds the shortest path between two locations. Understanding Queue deeply means understanding how real systems work.In this complete guide we will cover absolutely everything — what a Queue is, how it differs from a Stack, every type of Queue, all operations with code, Java implementations, time and space complexity, common interview questions, and the most important LeetCode problems that use Queue.What Is a Queue?A Queue is a linear data structure that follows the FIFO principle — First In First Out. This means the element that was added first is the one that gets removed first.Think of it exactly like a real-world queue (a line of people). The person who joined the line first gets served first. No cutting in line, no serving from the back — strict order from front to back.This is the fundamental difference between a Queue and a Stack:Stack → LIFO (Last In First Out) — like a stack of plates, you take from the topQueue → FIFO (First In First Out) — like a line of people, you serve from the frontReal Life Examples of QueueBefore writing a single line of code, let us understand where queues appear in real life. This will make every technical concept feel natural.Printer Queue — when you send multiple documents to print, they print in the order they were sent. The first document sent prints first.CPU Task Scheduling — your operating system manages running processes in a queue. Tasks get CPU time in the order they arrive (in basic scheduling).Customer Service Call Center — when you call a helpline and are put on hold, you are placed in a queue. The first caller on hold gets connected first.WhatsApp Messages — messages are delivered in the order they are sent. The first message sent is the first one received.BFS (Breadth First Search) — every time you use Google Maps or any navigation app to find the shortest path, it uses BFS internally which is entirely powered by a Queue.Ticket Booking Systems — online booking portals process requests in the order they arrive. First come first served.Queue Terminology — Key Terms You Must KnowBefore diving into code, let us get the vocabulary right:Front — the end from which elements are removed (dequeued). This is where the "first person in line" stands.Rear (or Back) — the end at which elements are added (enqueued). New arrivals join here.Enqueue — the operation of adding an element to the rear of the queue. Like joining the back of a line.Dequeue — the operation of removing an element from the front of the queue. Like the first person in line being served and leaving.Peek (or Front) — looking at the front element without removing it. Like seeing who is first in line without serving them yet.isEmpty — checking whether the queue has no elements.isFull — relevant for fixed-size queues, checking whether no more elements can be added.Types of QueuesThis is where most beginners get confused. There is not just one type of Queue — there are several variations each designed to solve specific problems.1. Simple Queue (Linear Queue)The most basic form. Elements enter from the rear and leave from the front. Strict FIFO, nothing fancy.Enqueue → [ 1 | 2 | 3 | 4 | 5 ] → Dequeue rear frontProblem with Simple Queue: In array-based implementation, once elements are dequeued from the front, those slots cannot be reused even if there is space. This wastes memory. This is why Circular Queue was invented.2. Circular QueueIn a Circular Queue, the rear wraps around to the front when it reaches the end of the array. The last position connects back to the first, forming a circle. This solves the wasted space problem of simple queues. [1] [2] [3] / \ [6] [4] \ / [5] ← rearUsed in: CPU scheduling, memory management, traffic light systems, streaming buffers.3. Double Ended Queue (Deque)A Deque (pronounced "deck") allows insertion and deletion from both ends — front and rear. It is the most flexible queue type.Enqueue Front → [ 1 | 2 | 3 | 4 | 5 ] → Dequeue FrontEnqueue Rear → [ 1 | 2 | 3 | 4 | 5 ] → Dequeue RearTwo subtypes:Input Restricted Deque — insertion only at rear, deletion from both endsOutput Restricted Deque — deletion only at front, insertion at both endsUsed in: browser history (back and forward), undo-redo operations, sliding window problems.4. Priority QueueElements are not served in FIFO order — instead each element has a priority and the element with the highest priority is served first regardless of when it was added.Think of an emergency room. A patient with a critical injury jumps ahead of someone with a minor cut even if they arrived later.Two types:Max Priority Queue — highest value = highest priorityMin Priority Queue — lowest value = highest priorityUsed in: Dijkstra's shortest path, Huffman encoding, A* search algorithm, task scheduling with priorities.5. Blocking QueueA thread-safe queue used in multi-threading. If the queue is empty, a thread trying to dequeue will wait (block) until an element is available. If the queue is full, a thread trying to enqueue will wait until space is available.Used in: Producer-Consumer problems, thread pool implementations, Java's java.util.concurrent package.Queue Operations and Time ComplexityEvery queue operation has a specific time complexity that you must know cold for interviews.OperationDescriptionTime ComplexityEnqueueAdd element to rearO(1)DequeueRemove element from frontO(1)Peek/FrontView front elementO(1)isEmptyCheck if queue is emptyO(1)SizeNumber of elementsO(1)SearchFind a specific elementO(n)Space Complexity: O(n) — where n is the number of elements stored.All core queue operations are O(1). This is what makes Queue so powerful — no matter how many elements are in the queue, adding and removing always takes constant time.Implementing Queue in Java — All WaysJava gives you multiple ways to use a Queue. Let us go through each one.Way 1: Using LinkedList (Most Common)LinkedList implements the Queue interface in Java. This is the most commonly used Queue implementation.import java.util.LinkedList;import java.util.Queue;Queue<Integer> queue = new LinkedList<>();// Enqueue — add to rearqueue.offer(10);queue.offer(20);queue.offer(30);// Peek — view front without removingSystem.out.println(queue.peek()); // 10// Dequeue — remove from frontSystem.out.println(queue.poll()); // 10System.out.println(queue.poll()); // 20// Check emptySystem.out.println(queue.isEmpty()); // false// SizeSystem.out.println(queue.size()); // 1offer() vs add() — both add to the queue. add() throws an exception if the queue is full (for bounded queues). offer() returns false instead. Always prefer offer().poll() vs remove() — both remove from front. remove() throws an exception if queue is empty. poll() returns null. Always prefer poll().peek() vs element() — both view the front. element() throws exception if empty. peek() returns null. Always prefer peek().Way 2: Using ArrayDeque (Fastest)ArrayDeque is faster than LinkedList for Queue operations because it uses a resizable array internally with no node allocation overhead.import java.util.ArrayDeque;import java.util.Queue;Queue<Integer> queue = new ArrayDeque<>();queue.offer(1);queue.offer(2);queue.offer(3);System.out.println(queue.peek()); // 1System.out.println(queue.poll()); // 1System.out.println(queue.size()); // 2When to use ArrayDeque over LinkedList? Use ArrayDeque whenever possible for Queue or Stack operations. It is faster because it avoids the overhead of node objects that LinkedList creates for every element. In competitive programming and interviews, ArrayDeque is the preferred choice.Way 3: Using Deque (Double Ended Queue)import java.util.ArrayDeque;import java.util.Deque;Deque<Integer> deque = new ArrayDeque<>();// Add to frontdeque.offerFirst(10);// Add to reardeque.offerLast(20);deque.offerLast(30);// Remove from frontSystem.out.println(deque.pollFirst()); // 10// Remove from rearSystem.out.println(deque.pollLast()); // 30// Peek front and rearSystem.out.println(deque.peekFirst()); // 20System.out.println(deque.peekLast()); // 20Way 4: Using PriorityQueueimport java.util.PriorityQueue;// Min Heap — smallest element has highest priorityPriorityQueue<Integer> minPQ = new PriorityQueue<>();minPQ.offer(30);minPQ.offer(10);minPQ.offer(20);System.out.println(minPQ.poll()); // 10 — smallest comes out first// Max Heap — largest element has highest priorityPriorityQueue<Integer> maxPQ = new PriorityQueue<>((a, b) -> b - a);maxPQ.offer(30);maxPQ.offer(10);maxPQ.offer(20);System.out.println(maxPQ.poll()); // 30 — largest comes out firstWay 5: Implementing Queue From Scratch Using ArrayUnderstanding the underlying implementation helps you in interviews when asked to build one from scratch.class MyQueue { private int[] arr; private int front; private int rear; private int size; private int capacity; public MyQueue(int capacity) { this.capacity = capacity; arr = new int[capacity]; front = 0; rear = -1; size = 0; } public void enqueue(int val) { if (size == capacity) { System.out.println("Queue is full!"); return; } rear = (rear + 1) % capacity; // circular wrapping arr[rear] = val; size++; } public int dequeue() { if (isEmpty()) { System.out.println("Queue is empty!"); return -1; } int val = arr[front]; front = (front + 1) % capacity; // circular wrapping size--; return val; } public int peek() { if (isEmpty()) return -1; return arr[front]; } public boolean isEmpty() { return size == 0; } public int size() { return size; }}Notice the % capacity in enqueue and dequeue — that is what makes it a Circular Queue. Without this, once the rear reaches the end of the array, you cannot add more even if front has moved forward and freed up space.Way 6: Implementing Queue Using Two StacksThis is a very popular interview question — implement a Queue using two stacks. The idea is to use one stack for enqueue and another for dequeue.class QueueUsingTwoStacks { Stack<Integer> s1 = new Stack<>(); // for enqueue Stack<Integer> s2 = new Stack<>(); // for dequeue public void enqueue(int val) { s1.push(val); // always push to s1 } public int dequeue() { if (s2.isEmpty()) { // transfer all elements from s1 to s2 // this reverses the order, giving FIFO behavior while (!s1.isEmpty()) { s2.push(s1.pop()); } } return s2.pop(); } public int peek() { if (s2.isEmpty()) { while (!s1.isEmpty()) { s2.push(s1.pop()); } } return s2.peek(); } public boolean isEmpty() { return s1.isEmpty() && s2.isEmpty(); }}Why does this work?When you transfer elements from s1 to s2, the order reverses. The element that was added first to s1 ends up on top of s2 — which means it gets dequeued first. FIFO achieved using two LIFOs!Amortized time complexity: Each element is pushed and popped at most twice (once in s1, once in s2). So dequeue is O(1) amortized even though individual calls might take O(n).This is LeetCode 232 — Implement Queue using Stacks.Queue vs Stack — Side by SideFeatureQueueStackPrincipleFIFO — First In First OutLIFO — Last In First OutInsert atRearTopRemove fromFrontTopReal lifeLine of peopleStack of platesJava classLinkedList, ArrayDequeStack, ArrayDequeMain useBFS, schedulingDFS, backtracking, parsingPeekFront elementTop elementBFS — The Most Important Application of QueueBreadth First Search (BFS) is the single most important algorithm that uses a Queue. Understanding BFS is why Queue matters so much in DSA.BFS explores a graph or tree level by level — all nodes at distance 1 first, then all at distance 2, and so on. A Queue naturally enforces this level-by-level behavior.public void bfs(int start, List<List<Integer>> graph) { Queue<Integer> queue = new LinkedList<>(); boolean[] visited = new boolean[graph.size()]; queue.offer(start); visited[start] = true; while (!queue.isEmpty()) { int node = queue.poll(); // process front node System.out.print(node + " "); for (int neighbor : graph.get(node)) { if (!visited[neighbor]) { visited[neighbor] = true; queue.offer(neighbor); // add unvisited neighbors to rear } } }}Why Queue and not Stack for BFS? Queue ensures you process all neighbors of a node before going deeper. Stack would take you deep into one path first — that is DFS, not BFS. The FIFO property is what guarantees level-by-level exploration.BFS with Queue is used in:Shortest path in unweighted graphsLevel order traversal of treesFinding connected componentsWord ladder problemsRotten oranges, flood fill, and matrix BFS problemsLevel Order Traversal — BFS on TreesOne of the most common Queue problems in interviews is Level Order Traversal of a binary tree.public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> result = new ArrayList<>(); if (root == null) return result; Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { int levelSize = queue.size(); // number of nodes at current level List<Integer> level = new ArrayList<>(); for (int i = 0; i < levelSize; i++) { TreeNode node = queue.poll(); level.add(node.val); if (node.left != null) queue.offer(node.left); if (node.right != null) queue.offer(node.right); } result.add(level); } return result;}The key trick here is using queue.size() at the start of each while loop iteration to know exactly how many nodes belong to the current level. Process exactly that many nodes, then move to the next level.This is LeetCode 102 — Binary Tree Level Order Traversal.Sliding Window Maximum — Monotonic DequeOne of the most impressive Queue applications is the Sliding Window Maximum problem using a Monotonic Deque. This is the queue equivalent of the Monotonic Stack pattern you saw in stack problems.The idea — maintain a deque that stores indices of elements in decreasing order. The front always holds the index of the maximum element in the current window.public int[] maxSlidingWindow(int[] nums, int k) { Deque<Integer> deque = new ArrayDeque<>(); // stores indices int[] result = new int[nums.length - k + 1]; int idx = 0; for (int i = 0; i < nums.length; i++) { // remove indices that are out of the current window while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) { deque.pollFirst(); } // remove indices whose values are smaller than current // they can never be the maximum for any future window while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) { deque.pollLast(); } deque.offerLast(i); // window is fully formed, record maximum (front of deque) if (i >= k - 1) { result[idx++] = nums[deque.peekFirst()]; } } return result;}This gives O(n) time for what would otherwise be an O(n×k) problem. This is LeetCode 239 — Sliding Window Maximum.Java Queue Interface — Complete Method ReferenceHere is every method you will ever need from Java's Queue and Deque interfaces:Queue Methods:offer(e) — add to rear, returns false if full (preferred over add) poll() — remove from front, returns null if empty (preferred over remove) peek() — view front without removing, returns null if empty (preferred over element) isEmpty() — returns true if no elements size() — returns number of elements contains(o) — returns true if element existsDeque Additional Methods:offerFirst(e) — add to front offerLast(e) — add to rear pollFirst() — remove from front pollLast() — remove from rear peekFirst() — view front peekLast() — view rearPriorityQueue Specific:offer(e) — add with natural ordering or custom comparator poll() — remove element with highest priority peek() — view highest priority element without removingCommon Interview Questions About QueueThese are the questions interviewers ask to test your understanding of queues conceptually — not just coding.Q1. What is the difference between Queue and Stack? Queue is FIFO — elements are removed in the order they were added. Stack is LIFO — the most recently added element is removed first. Queue removes from the front, Stack removes from the top.Q2. Why is ArrayDeque preferred over LinkedList for Queue in Java? ArrayDeque uses a resizable array internally and has better cache locality and no node allocation overhead. LinkedList creates a new node object for every element added, which means more garbage collection pressure. ArrayDeque is faster in practice for most Queue use cases.Q3. When would you use a PriorityQueue instead of a regular Queue? When the order of processing depends on priority rather than arrival order. For example in a hospital, critical patients are treated before minor cases regardless of when they arrived. Or in Dijkstra's algorithm, always processing the shortest known distance first.Q4. How is Queue used in BFS? BFS uses a Queue to explore nodes level by level. The starting node is enqueued first. Each time a node is dequeued, all its unvisited neighbors are enqueued. Since Queue is FIFO, all neighbors of a node are processed before going deeper — guaranteeing level-by-level exploration.Q5. What is the difference between poll() and remove() in Java Queue? Both remove the front element. remove() throws NoSuchElementException if the queue is empty. poll() returns null instead of throwing. Always use poll() for safer code.Q6. Can a Queue have duplicates? Yes. Queue does not have any restriction on duplicate values unlike Sets. The same value can appear multiple times in a Queue.Q7. What is a Blocking Queue and when is it used? A Blocking Queue is a thread-safe Queue used in multi-threaded applications. When a thread tries to dequeue from an empty queue, it blocks (waits) until an element is available. When a thread tries to enqueue into a full queue, it blocks until space is available. Used in Producer-Consumer patterns.Top LeetCode Problems on QueueHere are the most important LeetCode problems that use Queue — organized from beginner to advanced:Beginner Level:232. Implement Queue using Stacks — implement Queue with two stacks, classic interview question225. Implement Stack using Queues — reverse of 232, implement Stack using Queue933. Number of Recent Calls — sliding window with QueueIntermediate Level:102. Binary Tree Level Order Traversal — BFS on tree, must know107. Binary Tree Level Order Traversal II — same but bottom up994. Rotting Oranges — multi-source BFS on grid1091. Shortest Path in Binary Matrix — BFS shortest path542. 01 Matrix — multi-source BFS, distance to nearest 0127. Word Ladder — BFS on word graph, classicAdvanced Level:239. Sliding Window Maximum — monotonic deque, must know862. Shortest Subarray with Sum at Least K — monotonic deque with prefix sums407. Trapping Rain Water II — 3D BFS with priority queue787. Cheapest Flights Within K Stops — BFS with constraintsQueue Cheat Sheet — Everything at a GlanceCreate a Queue:Queue<Integer> q = new LinkedList<>(); // standardQueue<Integer> q = new ArrayDeque<>(); // faster, preferredDeque<Integer> dq = new ArrayDeque<>(); // double endedPriorityQueue<Integer> pq = new PriorityQueue<>(); // min heapPriorityQueue<Integer> pq = new PriorityQueue<>((a,b) -> b-a); // max heapCore Operations:q.offer(x); // enqueueq.poll(); // dequeueq.peek(); // front elementq.isEmpty(); // check emptyq.size(); // number of elementsDeque Operations:dq.offerFirst(x); // add to frontdq.offerLast(x); // add to reardq.pollFirst(); // remove from frontdq.pollLast(); // remove from reardq.peekFirst(); // view frontdq.peekLast(); // view rearBFS Template:Queue<Integer> queue = new LinkedList<>();queue.offer(start);visited[start] = true;while (!queue.isEmpty()) { int node = queue.poll(); for (int neighbor : graph.get(node)) { if (!visited[neighbor]) { visited[neighbor] = true; queue.offer(neighbor); } }}ConclusionQueue is one of those data structures that appears simple on the surface but has incredible depth once you start exploring its variations and applications. From the basic FIFO concept to Circular Queues, Deques, Priority Queues, Monotonic Deques, and BFS — each layer adds a new tool to your problem-solving arsenal.Here is the learning path to follow based on everything covered in this guide:Start with understanding FIFO vs LIFO and when each applies. Then get comfortable with Java's Queue interface — offer, poll, peek. Practice the BFS template until it feels automatic. Then move to Level Order Traversal problems. Once BFS clicks, tackle multi-source BFS problems like Rotting Oranges. Finally learn the Monotonic Deque pattern for sliding window problems.Master these and you will handle every Queue problem in any coding interview with confidence.

QueueData StructureJavaBFSDequePriority QueueCircular Queue

LeetCode 235: Lowest Common Ancestor of a Binary Search Tree – Java BST Solution with Dry Run

IntroductionLeetCode 235 – Lowest Common Ancestor of a Binary Search Tree is one of the most important BST interview problems.This problem helps you understand:Binary Search Tree propertiesRecursive traversalTree navigationAncestor relationshipsOptimized searchingIt is frequently asked in coding interviews because it combines tree traversal with BST optimization.Problem Link🔗 https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/Problem StatementGiven:Root of a Binary Search TreeTwo nodes p and qReturn:The Lowest Common Ancestor (LCA) of p and qThe LCA is the lowest node in the tree that has both nodes as descendants.A node can also be a descendant of itself.Example 1Inputroot = [6,2,8,0,4,7,9,null,null,3,5]p = 2q = 8Output6Example 2Inputroot = [6,2,8,0,4,7,9,null,null,3,5]p = 2q = 4Output2Understanding the BST PropertyA Binary Search Tree follows:Left Subtree < RootRight Subtree > RootExample: 6 / \ 2 8 / \ / \ 0 4 7 9 / \ 3 5This property allows us to find the LCA efficiently.Key ObservationThere are only three possible cases:Case 1Both nodes are smaller than root.Move LeftCase 2Both nodes are greater than root.Move RightCase 3One node is on the left and the other is on the right.OROne node equals root.Then:Current root is the LCAIntuitionSuppose:p = 2q = 8root = 6Now:2 < 68 > 6This means:One node is in left subtreeOne node is in right subtreeSo:6 is the first common split pointHence:6 is the Lowest Common AncestorBrute Force ApproachIdeaFind path from root to pFind path from root to qCompare both pathsLast common node is the LCABrute Force ComplexityTime ComplexityO(N)Space ComplexityO(N)Extra path storage required.Optimized BST ApproachUsing BST properties:No need to store pathsNo need to traverse entire treeMove intelligentlyThis gives a much cleaner solution.Java Solutionclass Solution { public TreeNode solve(TreeNode root, TreeNode p, TreeNode q) { if(root == null) return root; if(root.val < p.val && root.val < q.val) { return solve(root.right, p, q); } else if(root.val > p.val && root.val > q.val) { return solve(root.left, p, q); } else { return root; } } public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if(root == null) return root; return solve(root, p, q); }}Cleaner Recursive Versionclass Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if(root.val > p.val && root.val > q.val) { return lowestCommonAncestor(root.left, p, q); } if(root.val < p.val && root.val < q.val) { return lowestCommonAncestor(root.right, p, q); } return root; }}Iterative ApproachWe can also solve this without recursion.Iterative Java Solutionclass Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { while(root != null) { if(root.val > p.val && root.val > q.val) { root = root.left; } else if(root.val < p.val && root.val < q.val) { root = root.right; } else { return root; } } return null; }}Dry RunInputroot = [6,2,8,0,4,7,9,null,null,3,5]p = 2q = 8Step 1Current root:6Check:2 < 68 > 6One node is on left.One node is on right.So:6 is the LCAFinal Output6Another Dry RunInputp = 2q = 4Step 1Current root:6Both nodes smaller than 6.Move left.Step 2Current root:2Now:p == rootSo:2 is the LCAWhy This WorksBST ordering helps us eliminate half the tree at every step.If:p and q both smallerthen LCA must exist in left subtree.If:p and q both greaterthen LCA must exist in right subtree.Otherwise:Current node is the split pointwhich becomes the Lowest Common Ancestor.Time Complexity AnalysisOptimized BST SolutionAverage Time ComplexityO(log N)Because BST halves search space.Worst Case Time ComplexityO(N)Occurs when BST becomes skewed.Space ComplexityRecursiveO(H)Where:H = height of treeIterativeO(1)No recursion stack used.Interview ExplanationIn interviews, explain:Since this is a BST, we can use node ordering to decide whether both nodes lie in the left subtree, right subtree, or on different sides. The first split point becomes the Lowest Common Ancestor.This demonstrates:BST understandingTree recursionSearch optimizationEfficient traversal logicCommon Mistakes1. Treating It Like a Normal Binary TreeThis problem becomes easier because it is a BST.Use BST properties.2. Forgetting Split Point LogicThe LCA occurs when:p <= root <= qor vice versa.3. Traversing Entire TreeUnnecessary.BST lets us eliminate half the tree.4. Confusing Ancestor DefinitionA node can be ancestor of itself.Important for cases like:p = 2q = 4Answer becomes:2FAQsQ1. Why is BST important here?BST ordering allows efficient searching.Without BST property, we need a completely different approach.Q2. Can this be solved iteratively?Yes.Iterative traversal is even more space-efficient.Q3. Is recursion necessary?No.Both recursive and iterative solutions work.Q4. What is the Lowest Common Ancestor?The deepest node that has both target nodes as descendants.ConclusionLeetCode 235 is an excellent BST problem for mastering:BST propertiesRecursive traversalTree navigationOptimized searchingAncestor-based reasoningThe main insight is:In a BST, the first node where paths to p and q split becomes the Lowest Common Ancestor.Once this concept becomes intuitive, many BST interview problems become much easier to solve.

LeetCodeBinary Search TreeBSTJavaTreeMedium

LeetCode 98: Validate Binary Search Tree – Java DFS Recursive Solution Explained

IntroductionLeetCode 98 – Validate Binary Search Tree is one of the most important Binary Search Tree interview problems.This question is extremely popular because it tests:BST propertiesRecursive tree traversalDFS recursionRange validationTree constraints handlingMany beginners make mistakes on this problem because checking only parent-child relationships is not enough.Understanding the correct BST validation logic is very important for interviews.Problem Link🔗 https://leetcode.com/problems/validate-binary-search-tree/Problem StatementGiven the root of a binary tree, determine whether it is a valid Binary Search Tree (BST).A valid BST follows:Left subtree contains only smaller valuesRight subtree contains only greater valuesBoth left and right subtrees must also be BSTsExample 1Inputroot = [2,1,3]OutputtrueExplanation 2 / \ 1 3All BST conditions are satisfied.Example 2Inputroot = [5,1,4,null,null,3,6]OutputfalseWhy False? 5 / \ 1 4 / \ 3 6Although:4 < 6the node:4exists inside the right subtree of:5and should therefore be greater than 5.This violates BST rules.Key InsightThe most important understanding:Every node must satisfy an entire valid range, not just parent comparison.This is where many incorrect solutions fail.Common Wrong ThinkingMany beginners try:if(root.left.val < root.val && root.right.val > root.val)This is incorrect.Because BST validation depends on:ALL ancestor constraintsnot just immediate parent.Correct IntuitionEach node has:Minimum allowed valueMaximum allowed valueFor example:Left subtree -> values smaller than rootRight subtree -> values greater than rootAs recursion goes deeper:constraints become tighterVisual Understanding 10 / \ 5 15 / \ 6 20Node:6is invalid because:6 < 10even though:6 < 15This proves:Parent-only checking is insufficient.Brute Force ApproachIdeaFor every node:Find maximum in left subtreeFind minimum in right subtreeValidate BST conditionsBrute Force ComplexityTime ComplexityO(N²)Because subtree traversal repeats for every node.Space ComplexityO(H)Recursive stack space.Optimized Recursive DFS ApproachThe optimized idea:Pass valid range during recursion.Each node must satisfy:min < node.val < maxJava Solutionclass Solution { public boolean solve(TreeNode root, long min, long max) { if(root == null) return true; if(root.val <= min || root.val >= max) { return false; } return solve(root.left, min, root.val) && solve(root.right, root.val, max); } public boolean isValidBST(TreeNode root) { if(root == null) return true; return solve(root, Long.MIN_VALUE, Long.MAX_VALUE); }}Why Use Long Instead of Int?Constraints allow:-2³¹ <= Node.val <= 2³¹ - 1Using:Integer.MIN_VALUEInteger.MAX_VALUEcan create edge-case failures.So we safely use:Long.MIN_VALUELong.MAX_VALUEHow This WorksFor every node:Left SubtreeAllowed range:(min, root.val)Right SubtreeAllowed range:(root.val, max)This guarantees global BST validity.Dry RunInputroot = [2,1,3]Step 1Current node:2Allowed range:(-∞, +∞)Valid.Step 2Move left:1Allowed range:(-∞, 2)Valid.Step 3Move right:3Allowed range:(2, +∞)Valid.Final OutputtrueAnother Dry RunInputroot = [5,1,4,null,null,3,6]Step 1Node:5Range:(-∞, +∞)Valid.Step 2Move right to:4Range:(5, +∞)Now:4 <= 5Invalid BST.Final OutputfalseTime Complexity AnalysisTime ComplexityO(N)Every node visited once.Space ComplexityO(H)Where:H = height of treeWorst case:O(N)for skewed tree.Alternative Approach Using Inorder TraversalKey PropertyBST inorder traversal produces:strictly increasing orderInorder Java Solutionclass Solution { TreeNode prev = null; public boolean inorder(TreeNode root) { if(root == null) return true; if(!inorder(root.left)) return false; if(prev != null && root.val <= prev.val) { return false; } prev = root; return inorder(root.right); } public boolean isValidBST(TreeNode root) { return inorder(root); }}Interview ExplanationIn interviews, explain:A valid BST requires every node to satisfy ancestor constraints, not just parent constraints. Therefore, we recursively maintain valid minimum and maximum bounds for each node.This demonstrates:Deep BST understandingRecursive DFS masteryConstraint propagationEdge-case handlingCommon Mistakes1. Comparing Only Parent NodesIncorrect approach:root.left.val < root.valThis misses ancestor violations.2. Forgetting Strict InequalityBST requires:strictly smallerstrictly greaterDuplicates are invalid.3. Using int Instead of longCan fail on edge values.Always use:long minlong max4. Incorrect Range PassingCorrect recursion:left -> (min, root.val)right -> (root.val, max)FAQsQ1. Why does parent comparison fail?Because BST validity depends on all ancestor constraints.Q2. Why use min/max bounds?Bounds propagate BST restrictions correctly.Q3. Can inorder traversal solve this?Yes.BST inorder traversal must be strictly increasing.Q4. Is this asked frequently?Very frequently.It is one of the most important BST interview questions.Related ProblemsPractice these next:Search in BSTInsert into BSTLowest Common Ancestor in BSTKth Smallest Element in BSTConclusionLeetCode 98 is an excellent problem for mastering:BST validationRecursive DFSConstraint propagationTree traversalInterview problem-solvingThe key insight is:Every BST node must satisfy a valid global range, not just local parent conditions.Once this concept becomes intuitive, many advanced BST problems become significantly easier.

LeetCodeBinary Search TreeBSTJavaDFS TraversalBinary TreeRecursionMedium

LeetCode 2196: Create Binary Tree From Descriptions – Java HashMap & Tree Construction Solution

IntroductionBinary tree construction problems are extremely common in coding interviews because they test multiple concepts together:Tree data structuresHashMap usageParent-child relationshipsGraph-style thinkingRoot identificationLeetCode 2196 is an excellent medium-level problem that focuses on constructing a binary tree from parent-child descriptions efficiently.In this article, we will deeply understand:How the tree is formedHow to identify the root nodeWhy HashMap is useful hereStep-by-step dry runTime and space complexityComplete optimized Java solutionProblem StatementYou are given a 2D array:descriptions[i] = [parent, child, isLeft]Where:parent is the parent nodechild is the child nodeisLeft == 1 means left childisLeft == 0 means right childYour task is to:Construct the binary treeReturn the root nodeHere is the Link to try it now -: Create Binary Tree From DescriptionsExampleInputdescriptions = [ [20,15,1], [20,17,0], [50,20,1], [50,80,0], [80,19,1]]Output[50,20,80,15,17,19]Visual Representation 50 / \ 20 80 / \ / 15 17 19Key ObservationEvery node except the root appears as a child exactly once.This means:Root node never appears in child positionsIf we store all child nodes,The node not present in the child set becomes the rootThis is the core trick of the problem.Approach OverviewWe solve the problem in 3 steps:Step 1: Find the Root NodeStore every child node in a HashSet.Then iterate through descriptions again:The parent that never appears as a child is the root.Step 2: Create Tree NodesUse a HashMap:value → TreeNodeThis prevents duplicate node creation.Step 3: Connect Parent and ChildBased on:isLeftattach nodes accordingly.Optimized Java Solutionclass Solution { public TreeNode createBinaryTree(int[][] descriptions) { HashSet<Integer> childSet = new HashSet<>(); // Store all child nodes for (int[] arr : descriptions) { childSet.add(arr[1]); } // Find root node int rootValue = -1; for (int[] arr : descriptions) { if (!childSet.contains(arr[0])) { rootValue = arr[0]; } } // Map value -> TreeNode HashMap<Integer, TreeNode> map = new HashMap<>(); for (int i = 0; i < descriptions.length; i++) { int parent = descriptions[i][0]; int child = descriptions[i][1]; int isLeft = descriptions[i][2]; // Create parent node if absent if (!map.containsKey(parent)) { map.put(parent, new TreeNode(parent)); } // Create child node if absent if (!map.containsKey(child)) { map.put(child, new TreeNode(child)); } // Connect nodes if (isLeft == 1) { map.get(parent).left = map.get(child); } else { map.get(parent).right = map.get(child); } } return map.get(rootValue); }}Step-by-Step ExplanationStep 1: Store All Child NodeschildSet.add(arr[1]);Every child is stored.Since root never becomes a child,it will not exist inside this set.Step 2: Identify Rootif (!childSet.contains(arr[0]))This finds the node that only acts as parent.That node becomes the root.Step 3: Create Unique Tree NodesHashMap<Integer, TreeNode> mapAvoids duplicate node creation.Each value maps to exactly one TreeNode.Step 4: Connect Parent and Childmap.get(parent).left = map.get(child);ormap.get(parent).right = map.get(child);depending on:isLeftDry RunInput[ [20,15,1], [20,17,0], [50,20,1], [50,80,0], [80,19,1]]Child Set15, 17, 20, 80, 19Root DetectionCheck parents:20 → exists in child set50 → NOT in child setSo:Root = 50Tree Construction50left → 20right → 8020left → 15right → 1780left → 19Final tree becomes: 50 / \ 20 80 / \ / 15 17 19Time ComplexityBuilding Child SetO(N)Finding RootO(N)Constructing TreeO(N)Total Time ComplexityO(N)Efficient for large constraints.Space ComplexityHashMap + HashSetO(N)Why This Problem is ImportantThis problem teaches:Tree constructionParent-child mappingRoot identificationEfficient object reuseHashMap optimizationIt is frequently asked in interviews because it combines multiple concepts in one clean implementation.Common Mistakes1. Creating Duplicate NodesWrong:new TreeNode(parent)every time.Always reuse nodes through HashMap.2. Incorrect Root DetectionRemember:Root never appears as child.3. Forgetting Left vs Right ChildAlways check:isLeftbefore attaching.Interview TipsIn interviews explain:We first identify the root using a child set, then use a HashMap to create and reuse TreeNode objects efficiently while connecting parent-child relationships.This demonstrates:Strong data structure understandingEfficient memory usageClean tree construction logicRelated ProblemsPractice these next:Construct Binary Tree from TraversalsValidate Binary Search TreeSerialize and Deserialize Binary TreeLowest Common AncestorBinary Tree Level Order TraversalConclusionLeetCode 2196 is a clean and elegant binary tree construction problem.The major insight is:The root node is the only node that never appears as a child.Combined with HashMap-based node reuse, we can construct the entire tree efficiently in linear time.This is an excellent interview problem for mastering tree construction patterns.

LeetCodeJavaTreeHashMapHashSetBinary TreeMedium

LeetCode 701: Insert into a Binary Search Tree – Java Recursive Solution with Dry Run

IntroductionLeetCode 701 – Insert into a Binary Search Tree is one of the most important Binary Search Tree problems for coding interviews.This problem helps developers understand:BST propertiesRecursive traversalTree modificationNode insertion logicDFS recursionIt is frequently asked because BST insertion is a foundational concept used in:Search operationsTree balancingDatabase indexingOrdered data structuresProblem Link🔗 https://leetcode.com/problems/insert-into-a-binary-search-tree/Problem StatementYou are given:Root of a Binary Search TreeA value to insertReturn:Root of BST after insertionThe inserted value is guaranteed to be unique.What is a Binary Search Tree?A BST follows this rule:Left subtree values < RootRight subtree values > RootExample: 4 / \ 2 7 / \ 1 3If we insert:5It becomes: 4 / \ 2 7 / \ / 1 3 5Key ObservationWhile traversing:If value is smaller → go leftIf value is larger → go rightEventually:We reach a null positionThat is the insertion point.IntuitionBST insertion behaves exactly like BST search.We recursively move:left or rightuntil we find:nullThen create the new node there.Brute Force ThinkingA beginner might think:Store tree in arrayInsert valueSort againRebuild BSTBut rebuilding the tree is unnecessary and inefficient.BST already provides ordered traversal naturally.Optimized Recursive ApproachIdeaAt every node:If value is smaller → insert into left subtreeElse → insert into right subtreeWhen root becomes:nullcreate a new node.Java Solutionclass Solution { public void solve(TreeNode root, TreeNode prevnode, int val) { if(root == null) { if(prevnode.val < val) { prevnode.right = new TreeNode(val); } else { prevnode.left = new TreeNode(val); } return; } if(root.val > val) { solve(root.left, root, val); } else { solve(root.right, root, val); } } public TreeNode insertIntoBST(TreeNode root, int val) { if(root == null) { return new TreeNode(val); } TreeNode originalRoot = root; solve(root, root, val); return originalRoot; }}Cleaner Recursive Versionclass Solution { public TreeNode insertIntoBST(TreeNode root, int val) { if(root == null) { return new TreeNode(val); } if(val < root.val) { root.left = insertIntoBST(root.left, val); } else { root.right = insertIntoBST(root.right, val); } return root; }}Why This WorksBST property guarantees:Smaller values go leftLarger values go rightSo recursion naturally finds the correct insertion position.When recursion reaches:nullwe create the new node.Dry RunInputroot = [4,2,7,1,3]val = 5Step 1Current node:4Since:5 > 4move right.Step 2Current node:7Since:5 < 7move left.Step 3Left child is:nullInsert:5Final Tree 4 / \ 2 7 / \ / 1 3 5Time Complexity AnalysisAverage CaseTime ComplexityO(log N)Balanced BST height remains logarithmic.Space ComplexityO(log N)due to recursion stack.Worst CaseIf BST becomes skewed:1 -> 2 -> 3 -> 4Then:Time ComplexityO(N)Space ComplexityO(N)Recursive vs IterativeApproachTime ComplexitySpace ComplexityRecursiveO(H)O(H)IterativeO(H)O(1)Where:H = height of BSTIterative Java Solutionclass Solution { public TreeNode insertIntoBST(TreeNode root, int val) { if(root == null) { return new TreeNode(val); } TreeNode curr = root; while(true) { if(val < curr.val) { if(curr.left == null) { curr.left = new TreeNode(val); break; } curr = curr.left; } else { if(curr.right == null) { curr.right = new TreeNode(val); break; } curr = curr.right; } } return root; }}Interview ExplanationIn interviews, explain:Binary Search Tree insertion follows BST ordering rules. We recursively traverse left or right depending on the value until we reach a null node, where the new node is inserted.This demonstrates:BST understandingRecursive traversalTree manipulationDFS logicCommon Mistakes1. Forgetting to Return RootAlways return original root after insertion.2. Breaking BST PropertyIncorrect comparisons can violate BST ordering.Correct logic:if(val < root.val)3. Missing Base CaseWithout:if(root == null)recursion never stops.4. Rebuilding Entire TreeInsertion should modify existing BST directly.FAQsQ1. Why use recursion?BST naturally divides into smaller subtrees.Recursion simplifies traversal logic.Q2. Can insertion be iterative?Yes.Using loops avoids recursion stack usage.Q3. Why does BST insertion work efficiently?Because BST reduces search space at every step.Q4. Is this problem important for interviews?Absolutely.BST insertion is one of the most frequently asked tree concepts.ConclusionLeetCode 701 is an excellent BST problem for learning:Recursive tree traversalBST propertiesNode insertion logicDFS recursionThe core insight is:Move left for smaller values and right for larger values until a null position is found.Once this becomes intuitive, most BST operations become much easier to solve.

LeetCodeBSTBinary Search TreeJavaRecursionTreeMedium

Ceil in BST – Java Recursive Binary Search Tree Solution with Dry Run

IntroductionThe Ceil in BST problem is one of the most important Binary Search Tree interview questions.This problem teaches:BST traversalRecursive searchingDecision making using BST propertiesTree optimizationInterview-level recursion conceptsThe main challenge is understanding how BST ordering helps us efficiently locate the smallest value greater than or equal to a target number.Problem Link🔗 GeeksforGeeks – Ceil in BSTProblem StatementGiven a Binary Search Tree and an integer:xfind the:Ceil(x)The ceil of a number is:The smallest value in the BST that is greater than or equal to x.If no such value exists:return -1Example 1Inputroot = [5,1,7,N,2,N,N,N,3]x = 3Output3ExplanationSince:3 exists in the BSTthe ceil is:3Example 2Inputroot = [10,5,11,4,7,N,N,N,N,N,8]x = 6Output7ExplanationThe smallest value greater than or equal to:6is:7Key ObservationBinary Search Trees follow:Left subtree -> smaller valuesRight subtree -> greater valuesThis allows efficient searching.IntuitionSuppose:x = 6and current node is:10Since:10 > 6this node can potentially be the answer.But maybe a smaller valid ceil exists in the left subtree.So:Store current node as possible answerMove leftImportant BST LogicIf:root.data == xWe found exact ceil.Return immediately.If:root.data > xCurrent node can be ceil.Move left to find smaller possible ceil.If:root.data < xCurrent node cannot be ceil.Move right.Brute Force ApproachIdeaTraverse the entire BST:Store all values greater than or equal to xReturn minimum among themBrute Force ComplexityTime ComplexityO(N)Space ComplexityO(N)If storing elements.Optimized BST Recursive ApproachUsing BST properties:Ignore unnecessary branchesSearch intelligentlyReduce traversal workJava Solutionclass Solution { int c = -1; int solve(Node root, int x, int c) { if(root == null) return c; if(root.data == x) return root.data; if(root.data > x) { c = root.data; return solve(root.left, x, c); } else { return solve(root.right, x, c); } } int findCeil(Node root, int x) { return solve(root, x, c); }}How the Solution WorksThe recursion maintains:current best ceil candidateWhenever:root.data > xupdate ceil candidate.Then search left subtree for smaller valid answer.Dry RunInput 10 / \ 5 11 / \ 4 7 \ 8x = 6Step 1Current node:10Since:10 > 6Possible ceil:10Move left.Step 2Current node:5Since:5 < 6Move right.Step 3Current node:7Since:7 > 6Update ceil:7Move left.Step 4Left child is null.Return:7Final Answer7Optimized Iterative ApproachYou can also solve this iteratively.Iterative Java Solutionclass Solution { int findCeil(Node root, int x) { int ceil = -1; while(root != null) { if(root.data == x) { return root.data; } if(root.data > x) { ceil = root.data; root = root.left; } else { root = root.right; } } return ceil; }}Why Iterative is BetterIterative solution avoids recursion stack.Better for:Large treesMemory optimizationInterview follow-up questionsTime Complexity AnalysisBest CaseO(log N)Balanced BST.Worst CaseO(N)Skewed BST.Space ComplexityRecursiveO(H)Recursion stack.IterativeO(1)Extra space.Interview ExplanationIn interviews explain:Since BST maintains sorted ordering, we can intelligently move left or right. Whenever a node is greater than x, it becomes a potential ceil candidate.This demonstrates:BST understandingRecursive reasoningSearch optimizationEfficient traversal logicCommon Mistakes1. Traversing Entire TreeUnnecessary because BST already provides ordering.2. Not Updating Ceil ProperlyAlways update:ceil = root.databefore moving left.3. Returning First Greater ElementNeed the:smallest greater valuenot just any greater value.4. Ignoring Exact MatchIf:root.data == xreturn immediately.FAQsQ1. What is ceil in BST?Smallest value greater than or equal to x.Q2. Why move left after finding larger value?To search for a smaller valid ceil.Q3. Can this be solved iteratively?Yes.Iterative solution is highly optimized.Q4. What if ceil does not exist?Return:-1Related BST ProblemsPractice these next:Search in BSTInsert into BSTKth Smallest in BSTLowest Common Ancestor in BSTConclusionCeil in BST is an excellent problem for learning:BST traversalRecursive decision makingSearch optimizationInterview tree logicThe key insight is:Whenever a node is greater than x, it becomes a potential answer, but a smaller valid ceil may still exist in the left subtree.Mastering this concept makes many BST interview problems significantly easier.

Binary Search TreeBSTJavaRecursionGFGMedium

Floor in BST – Java Recursive Binary Search Tree Solution with Dry Run

IntroductionThe Floor in BST problem is one of the most important Binary Search Tree interview questions for beginners.This problem helps you understand:BST traversalRecursive searchingTree optimizationDecision making using BST propertiesEfficient searching techniquesThe main idea is to efficiently find the:Greatest value smaller than or equal to k.Problem Link🔗 GeeksforGeeks – Floor in BSTProblem StatementGiven the root of a Binary Search Tree and an integer:kfind the:Floor(k)The floor of a number is:The greatest value in the BST that is less than or equal to k.If no such value exists:return -1Example 1Inputroot = [10,7,15,2,8,11,16]k = 14Output11ExplanationThe largest value smaller than or equal to:14is:11Example 2Inputroot = [5,2,12,1,3,9,21,null,null,null,null,null,null,19,25]k = 24Output21Key ObservationBinary Search Tree follows:Left subtree -> smaller valuesRight subtree -> greater valuesThis ordering allows optimized searching.IntuitionSuppose:k = 14and current node is:10Since:10 < 14this node can potentially be the floor.But maybe there exists a larger valid floor in the right subtree.So:Store current node as possible answerMove rightBST LogicCase 1If:root.data == kthen exact floor exists.Return immediately.Case 2If:root.data > kcurrent node cannot be floor.Move left.Case 3If:root.data < kcurrent node becomes possible floor.Move right to search for larger valid answer.Brute Force ApproachIdeaTraverse the entire BST:Store all values smaller than or equal to kReturn maximum among themBrute Force ComplexityTime ComplexityO(N)Space ComplexityO(N)If storing nodes.Optimized Recursive BST ApproachUsing BST properties:Ignore unnecessary branchesSearch efficientlyReduce traversal operationsJava Solutionclass Solution { int f = -1; public int findMaxFork(Node root, int k) { if(root == null) return f; if(root.data == k) return root.data; if(root.data > k) { return findMaxFork(root.left, k); } else { f = root.data; return findMaxFork(root.right, k); } }}How the Solution WorksWhenever:root.data < kthe node becomes a possible floor candidate.But there may exist a larger valid floor in the right subtree.So:Save current nodeMove rightDry RunInput 10 / \ 7 15 / \ / \ 2 8 11 16k = 14Step 1Current node:10Since:10 < 14Possible floor:10Move right.Step 2Current node:15Since:15 > 14Move left.Step 3Current node:11Since:11 < 14Update floor:11Move right.Step 4Right child is null.Return:11Final Answer11Optimized Iterative ApproachThe same problem can also be solved iteratively.Iterative Java Solutionclass Solution { int findFloor(Node root, int k) { int floor = -1; while(root != null) { if(root.data == k) { return root.data; } if(root.data > k) { root = root.left; } else { floor = root.data; root = root.right; } } return floor; }}Why Iterative Approach is BetterAdvantages:Avoids recursion stackMore memory efficientBetter for skewed treesPreferred in some interviewsTime Complexity AnalysisBest CaseO(log N)Balanced BST.Worst CaseO(N)Skewed BST.Space ComplexityRecursiveO(H)where H is tree height.IterativeO(1)extra space.Interview ExplanationIn interviews explain:Whenever we encounter a node smaller than k, it becomes a possible floor candidate. Then we move right to search for a larger valid floor.This demonstrates:BST property understandingSearch optimizationRecursive reasoningEfficient traversalCommon Mistakes1. Traversing Entire TreeBST ordering already helps reduce search space.2. Forgetting to Update FloorAlways update:floor = root.databefore moving right.3. Returning First Smaller ValueNeed the:largest smaller valuenot any smaller value.4. Ignoring Exact MatchIf:root.data == kreturn immediately.FAQsQ1. What is floor in BST?Largest value smaller than or equal to k.Q2. Why move right after finding smaller value?To search for a larger valid floor.Q3. Can this be solved iteratively?Yes.Iterative solution is highly optimized.Q4. What if floor does not exist?Return:-1Related BST ProblemsPractice these next:Ceil in BSTSearch in BSTInsert into BSTValidate BSTLowest Common Ancestor in BSTConclusionFloor in BST is an excellent problem for understanding:BST traversalRecursive searchingSearch space optimizationInterview tree conceptsThe key insight is:Whenever a node is smaller than k, it becomes a possible floor candidate, but a larger valid floor may still exist in the right subtree.Mastering this logic makes many BST interview problems much easier.

BSTBinary Search TreeJavaGFGRecursionTree Data StructureEasy

LeetCode 450: Delete Node in a BST – Java Optimized Recursive Solution with Dry Run

IntroductionThe Delete Node in a BST problem is one of the most important Binary Search Tree interview questions because it combines:BST traversalTree restructuringRecursive thinkingNode replacement logicTree manipulationUnlike searching or insertion, deletion is slightly more complex because we must maintain BST properties after removing a node.This problem is frequently asked in coding interviews and online assessments.Problem Link🔗 LeetCode 450 – Delete Node in a BSTProblem StatementGiven:The root of a Binary Search TreeA key valueDelete the node containing the key while preserving BST properties.Return the updated BST root.BST Property ReminderIn a Binary Search Tree:Left subtree -> smaller valuesRight subtree -> greater valuesAfter deletion:Tree must still remain a valid BST.Example 1Inputroot = [5,3,6,2,4,null,7]key = 3Output[5,4,6,2,null,null,7]VisualizationBefore deletion: 5 / \ 3 6 / \ \ 2 4 7After deleting 3: 5 / \ 4 6 / \ 2 7Key Deletion CasesBST deletion has 3 important cases.Case 1: Node Has No ChildSimply remove the node.Case 2: Node Has One ChildReplace the node with its child.Case 3: Node Has Two ChildrenThis is the tricky part.We:Find inorder predecessor or successorReplace nodeReconnect subtrees properlyIntuitionSuppose we want to delete:3from: 5 / \ 3 6 / \ 2 4Since node 3 has:Left childRight childwe cannot directly delete it.Instead:Attach right subtree to rightmost node of left subtreeReturn left subtree as replacementThis preserves BST ordering.Brute Force ApproachIdeaStore inorder traversalRemove target nodeRebuild BSTWhy Brute Force is BadProblems:Extra memory usageRebuilding tree is expensiveUnnecessary traversalBrute Force ComplexityTime ComplexityO(N)Space ComplexityO(N)Optimized BST Deletion ApproachUse BST properties to:Search efficientlyModify only required nodesPreserve tree structureJava Solutionclass Solution { public TreeNode deleteNode(TreeNode root, int key) { if(root == null) return root; if(root.val == key) return solve(root); TreeNode originalRoot = root; while(root != null) { if(root.val > key) { if(root.left != null && root.left.val == key) { root.left = solve(root.left); } else { root = root.left; } } else { if(root.right != null && root.right.val == key) { root.right = solve(root.right); } else { root = root.right; } } } return originalRoot; } public TreeNode solve(TreeNode root) { if(root.left == null) return root.right; if(root.right == null) return root.left; TreeNode rightChild = root.right; TreeNode leftChild = asright(root.left); leftChild.right = rightChild; return root.left; } public TreeNode asright(TreeNode root) { if(root.right == null) return root; return asright(root.right); }}How This Solution WorksThe main logic happens inside:solve(root)This function deletes the node safely.Understanding solve()Case 1If:root.left == nullreturn right subtree.Case 2If:root.right == nullreturn left subtree.Case 3If both children exist:Save right subtreeFind rightmost node in left subtreeAttach right subtree thereReturn left subtreeWhy Rightmost Node?Because:Rightmost node of left subtreeis the:largest node smaller than rootThis maintains BST ordering perfectly.Dry RunInput 5 / \ 3 6 / \ \ 2 4 7key = 3Step 1Search node:3Step 2Node has:Left child = 2Right child = 4Step 3Find rightmost node in left subtree.Rightmost node:2Step 4Attach right subtree:2.right = 4Step 5Return left subtree:2Updated BST becomes valid.Time Complexity AnalysisBest CaseO(log N)Balanced BST.Worst CaseO(N)Skewed BST.Space ComplexityRecursive HelperO(H)where:H = tree heightAlternative Recursive ApproachAnother common method:Replace node with inorder successorDelete successor recursivelyThis approach is also interview friendly.Interview ExplanationIn interviews explain:When deleting a node with two children, we preserve BST properties by connecting the right subtree to the rightmost node of the left subtree.This demonstrates:BST restructuring knowledgeTree manipulation skillsRecursive reasoningPointer managementCommon Mistakes1. Forgetting BST PropertyDeletion should not break ordering.2. Losing SubtreesAlways reconnect children carefully.3. Incorrect Node ReplacementMany candidates replace node incorrectly.4. Not Handling Null CasesAlways check:root == nullproperly.FAQsQ1. Why is BST deletion difficult?Because tree structure must remain valid after removal.Q2. Why use rightmost node of left subtree?It is the largest smaller value.Perfect replacement candidate.Q3. Can we use inorder successor instead?Yes.Both predecessor and successor approaches work.Q4. What is deletion complexity?Balanced BST:O(log N)Worst case:O(N)Related BST ProblemsPractice these next:Insert into BSTSearch in BSTValidate BSTLowest Common Ancestor in BSTKth Smallest Element in BSTInorder Successor in BSTConclusionDelete Node in BST is one of the most important BST interview problems because it teaches:Tree restructuringRecursive manipulationPointer handlingBST property maintenanceThe key insight is:When deleting a node with two children, reconnect subtrees carefully so BST ordering remains valid.Mastering this problem makes advanced BST operations significantly easier.

BSTJavaBinary Search TreeLeetCodeTreeRecursionMedium

LeetCode 543: Diameter of Binary Tree – Java DFS Solution Explained

IntroductionLeetCode 543 – Diameter of Binary Tree is one of the most popular binary tree interview problems.This problem teaches:Depth First Search (DFS)Tree height calculationRecursive traversalBottom-up recursionTree optimization techniquesIt is extremely important because it introduces a very common pattern in tree problems:Use recursion to calculate subtree heights while simultaneously updating a global answer.This same idea is used in:Balanced Binary TreeMaximum Path SumLongest ZigZag PathTree DP problemsProblem Link🔗 https://leetcode.com/problems/diameter-of-binary-tree/Problem StatementGiven the root of a binary tree:Return:Length of the diameter of the treeThe diameter is:The length of the longest path between any two nodes in the tree.This path:May pass through the rootMay not pass through the rootImportant NoteThe diameter is measured in:EDGESnot nodes.Example 1Inputroot = [1,2,3,4,5]Tree: 1 / \ 2 3 / \ 4 5Output3Explanation:Longest path:4 → 2 → 1 → 3Edges count:3Example 2Inputroot = [1,2]Tree: 1 / 2Output:1Understanding DiameterAt every node:Possible longest path through that node is:left subtree height + right subtree heightWhy?Because:One side contributes left edgesOther side contributes right edgesTogether they form a path.Key ObservationFor every node:Diameter through node=leftHeight + rightHeightWe compute this for all nodes.Maximum among them becomes answer.Brute Force ApproachIntuitionFor every node:Calculate left subtree heightCalculate right subtree heightCompute diameterRecursively repeat for childrenBrute Force ComplexityHeight gets recalculated repeatedly.Time ComplexityO(N²)Space ComplexityO(H)where:H = tree heightOptimized DFS ApproachInstead of separately calculating:HeightDiameterWe calculate both in one DFS traversal.Core IdeaWhile calculating subtree height:We also update:max diameterThis avoids repeated traversal.Java Solutionclass Solution { int max = Integer.MIN_VALUE; public int solve(TreeNode roo) { if(roo == null) return 0; int left = solve(roo.left); int right = solve(roo.right); max = Math.max(max, left + right); return 1 + Math.max(left, right); } public int diameterOfBinaryTree(TreeNode root) { solve(root); return max; }}Cleaner Optimized Versionclass Solution { int diameter = 0; public int height(TreeNode root) { if(root == null) return 0; int left = height(root.left); int right = height(root.right); diameter = Math.max(diameter, left + right); return 1 + Math.max(left, right); } public int diameterOfBinaryTree(TreeNode root) { height(root); return diameter; }}Why This WorksAt every node:Find left subtree heightFind right subtree heightCompute:left + rightUpdate global maximum diameterReturn current subtree height upwardDry RunInput 1 / \ 2 3 / \ 4 5Step 1Leaf nodes:4 → height = 15 → height = 13 → height = 1Step 2At node:2Left height:1Right height:1Diameter through node:1 + 1 = 2Update:max = 2Height of node 2:2Step 3At root:1Left height:2Right height:1Diameter:2 + 1 = 3Update:max = 3Final Answer3Recursive Visualizationheight(1) ├── height(2) │ ├── height(4) │ └── height(5) │ └── height(3)Diameter gets updated during return phase.Time Complexity AnalysisOptimized DFS SolutionTime ComplexityO(N)because every node is visited once.Space ComplexityO(H)where:H = tree heightWorst case:O(N)for skewed tree.Brute Force vs OptimizedApproachTime ComplexitySpace ComplexityBrute ForceO(N²)O(H)Optimized DFSO(N)O(H)Interview ExplanationIn interviews, explain:While recursively calculating subtree heights, we simultaneously compute the maximum possible path passing through every node.This demonstrates:DFS understandingBottom-up recursionOptimization skillsTree DP thinkingCommon Mistakes1. Counting Nodes Instead of EdgesDiameter measures:edgesnot nodes.2. Forgetting Global VariableDiameter must be updated across all nodes.3. Returning Diameter Instead of HeightRecursive function should return:heightnot diameter.FAQsQ1. Does diameter always pass through root?No.It can exist completely inside a subtree.Q2. Why use DFS?Because height calculation naturally follows recursive depth traversal.Q3. Why update diameter globally?Because longest path may occur at any node.Q4. Is this problem important for interviews?Very important.It is one of the most common recursive tree questions.ConclusionLeetCode 543 is one of the best problems for learning recursive tree optimization.It teaches:DFS traversalHeight calculationBottom-up recursionGlobal answer trackingThe key insight is:Diameter through a node equals left subtree height + right subtree height.Once you understand this pattern, many advanced binary tree problems become much easier.

LeetCodeDiameter of Binary TreeJavaBinary TreeDFSTreeRecursionEasy

LeetCode 110: Balanced Binary Tree – Java Optimized DFS Solution Explained

IntroductionLeetCode 110 – Balanced Binary Tree is one of the most important binary tree interview problems.This problem teaches:Tree recursionHeight calculationDepth First Search (DFS)Bottom-up recursionOptimization techniquesIt is frequently asked in coding interviews because it checks whether you can:Traverse trees efficientlyAvoid repeated calculationsCombine recursion with conditionsOptimize brute force tree solutionsThis problem is also a foundation for advanced tree problems like:AVL TreesHeight-balanced treesDiameter of Binary TreeTree DP problemsProblem Link🔗 https://leetcode.com/problems/balanced-binary-tree/Problem StatementGiven the root of a binary tree:Return:trueif the tree is:height-balancedOtherwise return:falseWhat is a Balanced Binary Tree?A binary tree is balanced if:For every node,|height(left subtree) - height(right subtree)| <= 1Meaning:Left and right subtree heights should not differ by more than:1Example 1Inputroot = [3,9,20,null,null,15,7]Tree:3/ \9 20/ \15 7OutputtrueExplanation:Every node satisfies:height difference <= 1Example 2Inputroot = [1,2,2,3,3,null,null,4,4]Tree:1/ \2 2/ \3 3/ \4 4OutputfalseExplanation:Left subtree becomes much deeper than right subtree.Difference becomes greater than:1Key ObservationTo determine if tree is balanced:At every node we need:Height of left subtreeHeight of right subtreeCompare differenceThis naturally becomes a recursive DFS problem.Brute Force ApproachIntuitionFor every node:Calculate left heightCalculate right heightCompare differenceRecursively check childrenBrute Force Java Solutionclass Solution {public int height(TreeNode root) {if(root == null)return 0;return 1 + Math.max(height(root.left), height(root.right));}public boolean isBalanced(TreeNode root) {if(root == null)return true;int left = height(root.left);int right = height(root.right);if(Math.abs(left - right) > 1)return false;return isBalanced(root.left) && isBalanced(root.right);}}Problem with Brute ForceThe height function gets called repeatedly.For every node:Heights are recalculated again and again.This increases complexity significantly.Brute Force ComplexityTime ComplexityO(N²)because height calculation repeats.Space ComplexityO(H)for recursion stack.Optimized DFS ApproachInstead of:Calculating heights separatelyWe can:Calculate height and balance together.Core Optimization IdeaWhile calculating height:If subtree becomes unbalanced:Return negative value immediatelyThis avoids unnecessary computation.Optimized Java Solutionclass Solution {public int solve(TreeNode roo) {if(roo == null)return 0;int left = solve(roo.left);if(left < 0) {return -1;}int right = solve(roo.right);if(right < 0) {return -1;}if(Math.abs(left - right) > 1) {return -1000;}return 1 + Math.max(left, right);}public boolean isBalanced(TreeNode root) {int ans = solve(root);return ans < 0 ? false : true;}}Cleaner Optimized VersionWe can simplify negative returns using:-1consistently.Cleaner Java Solutionclass Solution {public int height(TreeNode root) {if(root == null)return 0;int left = height(root.left);if(left == -1)return -1;int right = height(root.right);if(right == -1)return -1;if(Math.abs(left - right) > 1)return -1;return 1 + Math.max(left, right);}public boolean isBalanced(TreeNode root) {return height(root) != -1;}}Why This WorksAt every node:Recursively calculate left heightRecursively calculate right heightIf difference > 1:Tree is unbalancedPropagate failure upward immediately.Dry RunInput1/ \2 2/ \3 3/ \4 4Step 1Start from leaf nodes:4 → height = 1Step 2Node:3gets:left = 1right = 1Difference:0Balanced.Height:2Step 3At node:2Left height:2Right height:0Difference:2Unbalanced.Return:-1Final ResultTree is:Not balancedReturn:falseTime Complexity AnalysisOptimized DFS SolutionTime ComplexityO(N)because every node is visited once.Space ComplexityO(H)where:H = height of treeWorst case:O(N)for skewed tree.Brute Force vs OptimizedApproachTime ComplexitySpace ComplexityBrute ForceO(N²)O(H)Optimized DFSO(N)O(H)Interview ExplanationIn interviews, explain:Instead of recalculating heights repeatedly, we combine height calculation and balance checking into a single DFS traversal.This demonstrates:Optimization skillsRecursive DFS understandingBottom-up tree processingCommon Mistakes1. Recalculating Heights RepeatedlyThis causes:O(N²)complexity.2. Forgetting Absolute DifferenceAlways use:Math.abs(left - right)3. Not Handling Null NodesBase case:if(root == null)return 0;is necessary.FAQsQ1. What is a balanced binary tree?A tree where left and right subtree heights differ by at most:1for every node.Q2. Why use DFS?Because height calculation naturally follows recursive depth traversal.Q3. Why return -1?It acts as a signal:Subtree already unbalancedQ4. Is this problem important for interviews?Very important.It is one of the most common tree optimization questions.ConclusionLeetCode 110 is an excellent binary tree optimization problem.It teaches:DFS traversalHeight calculationBottom-up recursionOptimization techniquesThe key insight is:Combine balance checking and height calculation in one DFS traversal.Once you understand this optimization pattern, many advanced tree problems become much easier.

LeetCodeBalanced Binary TreeJavaBinary TreeDFSTree HeightRecursionTree

Search in a Binary Search Tree (LeetCode 700) Java Solution with Explanation and Dry Run

IntroductionBinary Search Tree (BST) is one of the most important data structures frequently asked in coding interviews and competitive programming. LeetCode 700 - Search in a Binary Search Tree is a beginner-friendly problem that helps developers understand how BST properties can be utilized to perform efficient searches.In this article, we will discuss the problem statement, understand the BST property, develop an intuition, analyze the recursive solution, perform a dry run, and evaluate the time and space complexity.Problem StatementGiven the root of a Binary Search Tree (BST) and an integer value val, find the node whose value equals val and return the subtree rooted at that node.If the value does not exist in the BST, return null.Problem LinkLeetCode 700 - Search in a Binary Search TreeExample 1Input:root = [4,2,7,1,3]val = 2Output:[2,1,3]Explanation:The node with value 2 exists in the BST. Therefore, we return the subtree rooted at node 2.Example 2Input:root = [4,2,7,1,3]val = 5Output:[]Explanation:Value 5 does not exist in the BST, so we return null.Understanding the Binary Search Tree PropertyA Binary Search Tree follows these rules:All values in the left subtree are smaller than the root node.All values in the right subtree are greater than the root node.Both left and right subtrees are also BSTs.Example: 4 / \ 2 7 / \1 3Suppose we need to search for value 3:Start at 4.Since 3 < 4, move left.Reach node 2.Since 3 > 2, move right.Reach node 3.Value found.Instead of traversing every node, BST allows us to eliminate half of the search space at each step.IntuitionThe BST property gives us a clear direction while searching:If the current node's value equals val, return the node.If val is smaller than the current node's value, search in the left subtree.If val is greater than the current node's value, search in the right subtree.If we reach a null node, the value does not exist.This naturally leads to a recursive solution.ApproachAlgorithmIf the current node is null, return null.If the current node value equals val, return the node.If val is smaller than the current node value, recursively search the left subtree.Otherwise, recursively search the right subtree.Return the result obtained from recursion.Java Solutionclass Solution { public TreeNode solve(TreeNode root, int val) { if (root == null) return root; if (root.val == val) return root; if (root.val > val) { return solve(root.left, val); } else { return solve(root.right, val); } } public TreeNode searchBST(TreeNode root, int val) { if (root == null) return root; if (root.val == val) return root; return solve(root, val); }}Code ExplanationHelper Function: solve()This function recursively searches for the target value.if(root == null) return root;If the node is null, the value is not present.if(root.val == val) return root;If the value matches, return the current node.if(root.val > val) return solve(root.left, val);When the target value is smaller, move to the left subtree.return solve(root.right, val);When the target value is larger, move to the right subtree.Main Function: searchBST()if(root == null) return root;Handles the empty tree case.if(root.val == val) return root;If the root itself contains the target value, return immediately.return solve(root,val);Otherwise, begin recursive searching.Dry RunInput:root = [4,2,7,1,3]val = 2Tree: 4 / \ 2 7 / \1 3Step 1Current Node = 44 > 2Move to left subtree.Step 2Current Node = 22 == 2Target found.Return subtree: 2 / \1 3Output:[2,1,3]Another Dry RunInput:root = [4,2,7,1,3]val = 5Step 1Current Node = 45 > 4Move right.Step 2Current Node = 75 < 7Move left.Step 3Current Node = nullValue not found.Return null.Complexity AnalysisTime ComplexityBest Case:O(1)When the root itself contains the target value.Average Case:O(log n)For a balanced BST, each comparison reduces the search space by half.Worst Case:O(n)When the BST becomes skewed like a linked list.Space ComplexityO(h)Where h is the height of the tree due to recursive function calls.Balanced BST:O(log n)Skewed BST:O(n)Why This Solution WorksThe solution efficiently utilizes the Binary Search Tree property instead of performing a full tree traversal.At every node:Left subtree is searched only when necessary.Right subtree is searched only when necessary.Unnecessary branches are ignored.This significantly improves performance compared to a normal binary tree search.Interview TipsWhen solving BST search problems in interviews:Always mention the BST property first.Explain why only one subtree needs to be explored.Discuss both balanced and skewed tree scenarios.Mention iterative optimization if asked about reducing recursion stack space.ConclusionLeetCode 700 - Search in a Binary Search Tree is a fundamental BST problem that demonstrates how the ordered structure of a BST enables efficient searching. By leveraging BST properties, we can quickly locate a target node without traversing the entire tree.The recursive approach is simple, clean, and highly intuitive, making it an excellent solution for coding interviews and DSA practice. Understanding this problem builds a strong foundation for more advanced BST operations such as insertion, deletion, validation, and range queries.

LeetCodeBinary Search TreeJavaBSTEasyTreeRecursion

LeetCode 124: Binary Tree Maximum Path Sum – Java DFS Solution Explained

IntroductionLeetCode 124 – Binary Tree Maximum Path Sum is one of the most important and frequently asked hard-level binary tree interview problems.This problem teaches:Depth First Search (DFS)Bottom-up recursionTree Dynamic ProgrammingRecursive optimizationGlobal answer trackingIt is considered a classic interview problem because it combines:Tree traversalRecursive decision makingPath optimizationNegative value handlingMastering this problem helps in understanding advanced binary tree patterns used in:Diameter problemsTree DPMaximum path problemsGraph recursion problemsProblem Link🔗 https://leetcode.com/problems/binary-tree-maximum-path-sum/Problem StatementGiven the root of a binary tree:Return:Maximum path sum of any non-empty pathA path:Can start from any nodeCan end at any nodeMust follow parent-child connectionsCannot visit a node more than onceImportant:Path does NOT need to pass through rootExample 1Inputroot = [1,2,3]Tree: 1 / \ 2 3Output6Explanation:Best path:2 → 1 → 3Path sum:2 + 1 + 3 = 6Example 2Inputroot = [-10,9,20,null,null,15,7]Tree: -10 / \ 9 20 / \ 15 7Output42Explanation:Best path:15 → 20 → 7Sum:15 + 20 + 7 = 42Key ObservationAt every node:We have two important possibilities.Possibility 1Path continues upward to parent.In this case:We can choose only:ONE sidebecause path cannot split upward.Return value becomes:node + max(left, right)Possibility 2Current node becomes:Highest point of pathThen we can use:left + node + rightThis candidate updates global maximum answer.Core Recursive IdeaAt every node:Calculate left maximum contributionCalculate right maximum contributionIgnore negative pathsUpdate global answerReturn best single-side path upwardWhy Ignore Negative Paths?Negative paths reduce total sum.So:Math.max(path, 0)ensures:Negative contribution is discardedOnly profitable paths are consideredThis is the most important optimization.Your Java Solutionclass Solution { int max = Integer.MIN_VALUE; public int solve(TreeNode roo) { if(roo == null) return 0; int left = Math.max(solve(roo.left), 0); int right = Math.max(solve(roo.right), 0); max = Math.max(max, roo.val + left + right); return roo.val + Math.max(left, right); } public int maxPathSum(TreeNode root) { solve(root); return max; }}Why This WorksFor every node:We calculate:Best path passing through current nodewhich is:left + node + rightThis path may become global maximum.But while returning upward:We can only choose:one directionbecause paths cannot split.Dry RunInput -10 / \ 9 20 / \ 15 7Step 1Leaf nodes:9 → return 915 → return 157 → return 7Step 2At node:20Left:15Right:7Current best path:15 + 20 + 7 = 42Update:max = 42Return upward:20 + max(15,7)= 35Step 3At node:-10Left:9Right:35Candidate:9 + (-10) + 35 = 34Global maximum remains:42Final Answer42Recursive Visualizationsolve(-10) ├── solve(9) │ └── solve(20) ├── solve(15) └── solve(7)Global maximum gets updated during return phase.Brute Force ApproachA brute force approach would:Generate all possible pathsCalculate sumsTrack maximumBut number of paths becomes extremely large.This is inefficient.Brute Force ComplexityTime ComplexityCan become:O(N²)or worse depending on implementation.Optimized DFS ComplexityTime ComplexityO(N)because every node is visited once.Space ComplexityO(H)where:H = height of treeWorst case:O(N)for skewed tree.Important InsightTwo values exist at every node.1. Value Returned UpwardOnly one side allowed:node + max(left, right)2. Value Used for Global MaximumBoth sides allowed:left + node + rightThis distinction is the heart of the problem.Interview ExplanationIn interviews, explain:Every node acts as a potential highest point of a path. We compute the best path through that node while recursively returning the best single-side contribution upward.This demonstrates:Advanced DFS understandingTree DP conceptsRecursive optimizationHandling negative pathsCommon Mistakes1. Returning Both Sides UpwardIncorrect:left + node + rightA path cannot branch upward.2. Forgetting Negative Path HandlingAlways use:Math.max(value, 0)3. Assuming Path Must Pass RootThe path can exist entirely inside a subtree.4. Not Using Global VariableMaximum path may occur anywhere.FAQsQ1. Does path need to start from root?No.It can start and end anywhere.Q2. Why ignore negative sums?Negative paths reduce overall answer.Q3. Why can we return only one side?Because a path moving upward cannot split into two directions.Q4. Is this problem important for interviews?Extremely important.It is one of the most famous hard-level tree problems.Related ProblemsAfter mastering this problem, practice:Diameter of Binary TreeBalanced Binary TreeMaximum Depth of Binary TreeConclusionLeetCode 124 is one of the best problems for learning advanced binary tree recursion.It teaches:DFS optimizationTree dynamic programmingRecursive decision makingNegative path handlingGlobal answer trackingThe key insight is:Every node can become the highest point of a maximum path.Once this recursive pattern becomes clear, many advanced tree and graph problems become much easier to solve.

LeetCodeBinary Tree Maximum Path SumJavaBinary TreeDFSTreeRecursionDynamic Programming on TreesHard

Recursion in Java - Complete Guide With Examples and Practice Problems

IntroductionIf there is one topic in programming that confuses beginners more than anything else, it is recursion. Most people read the definition, nod their head, and then immediately freeze when they have to write recursive code themselves.The problem is not that recursion is genuinely hard. The problem is that most explanations start with code before building the right mental model. Once you have the right mental model, recursion clicks permanently and you start seeing it everywhere — in tree problems, graph problems, backtracking, dynamic programming, divide and conquer, and more.This guide covers everything from the ground up. What recursion is, how the call stack works, how to identify base cases and recursive cases, every type of recursion, common patterns, time and space complexity analysis, the most common mistakes, and the top LeetCode problems to practice.By the end of this article, recursion will not feel like magic anymore. It will feel like a natural tool you reach for confidently.What Is Recursion?Recursion is when a function calls itself to solve a smaller version of the same problem.That is the complete definition. But let us make it concrete.Imagine you want to count down from 5 to 1. One way is a loop. Another way is — print 5, then solve the exact same problem for counting down from 4 to 1. Then print 4, solve for 3. And so on until you reach the base — there is nothing left to count down.void countDown(int n) { if (n == 0) return; // stop here System.out.println(n); countDown(n - 1); // solve the smaller version}The function countDown calls itself with a smaller input each time. Eventually it reaches 0 and stops. That stopping condition is the most important part of any recursive function — the base case.The Two Parts Every Recursive Function Must HaveEvery correctly written recursive function has exactly two parts. Without both, the function either gives wrong answers or runs forever.Part 1: Base CaseThe base case is the condition under which the function stops calling itself and returns a direct answer. It is the smallest version of the problem that you can solve without any further recursion.Without a base case, recursion never stops and you get a StackOverflowError — Java's way of telling you the call stack ran out of memory.Part 2: Recursive CaseThe recursive case is where the function calls itself with a smaller or simpler input — moving closer to the base case with each call. If your recursive case does not make the problem smaller, you have an infinite loop.Think of it like a staircase. The base case is the ground floor. The recursive case is each step going down. Every step must genuinely bring you one level closer to the ground.How Recursion Works — The Call StackThis is the mental model that most explanations skip, and it is the reason recursion confuses people.Every time a function is called in Java, a new stack frame is created and pushed onto the call stack. This frame stores the function's local variables, parameters, and where to return to when the function finishes.When a recursive function calls itself, a new frame is pushed on top. When that call finishes, its frame is popped and execution returns to the previous frame.Let us trace countDown(3) through the call stack:countDown(3) called → frame pushed prints 3 calls countDown(2) → frame pushed prints 2 calls countDown(1) → frame pushed prints 1 calls countDown(0) → frame pushed n == 0, return → frame popped back in countDown(1), return → frame popped back in countDown(2), return → frame popped back in countDown(3), return → frame poppedOutput: 3, 2, 1The call stack grows as calls go deeper, then shrinks as calls return. This is why recursion uses O(n) space for n levels deep — each level occupies one stack frame in memory.Your First Real Recursive Function — FactorialFactorial is the classic first recursion example. n! = n × (n-1) × (n-2) × ... × 1Notice the pattern — n! = n × (n-1)!. The factorial of n is n times the factorial of n-1. That recursive structure makes it perfect for recursion.public int factorial(int n) { // base case if (n == 0 || n == 1) return 1; // recursive case return n * factorial(n - 1);}Dry Run — factorial(4)factorial(4)= 4 * factorial(3)= 4 * 3 * factorial(2)= 4 * 3 * 2 * factorial(1)= 4 * 3 * 2 * 1= 24The call stack builds up going in, then multiplications happen coming back out. This "coming back out" phase is called the return phase or unwinding of the stack.Time Complexity: O(n) — n recursive calls Space Complexity: O(n) — n frames on the call stackThe Two Phases of RecursionEvery recursive function has two phases and understanding both is critical.Phase 1: The Call Phase (Going In)This happens as the function keeps calling itself with smaller inputs. Things you do before the recursive call happen in this phase — in order from the outermost call to the innermost.Phase 2: The Return Phase (Coming Back Out)This happens as each call finishes and returns to its caller. Things you do after the recursive call happen in this phase — in reverse order, from the innermost call back to the outermost.This distinction explains why the output order can be surprising:void printBothPhases(int n) { if (n == 0) return; System.out.println("Going in: " + n); // call phase printBothPhases(n - 1); System.out.println("Coming out: " + n); // return phase}For printBothPhases(3):Going in: 3Going in: 2Going in: 1Coming out: 1Coming out: 2Coming out: 3This two-phase understanding is what makes problems like reversing a string or printing a linked list backwards via recursion feel natural.Types of RecursionRecursion is not one-size-fits-all. There are several distinct types and knowing which type applies to a problem shapes how you write the solution.1. Direct RecursionThe function calls itself directly. This is the most common type — what we have seen so far.void direct(int n) { if (n == 0) return; direct(n - 1); // calls itself}2. Indirect RecursionFunction A calls Function B which calls Function A. They form a cycle.void funcA(int n) { if (n <= 0) return; System.out.println("A: " + n); funcB(n - 1);}void funcB(int n) { if (n <= 0) return; System.out.println("B: " + n); funcA(n - 1);}Used in: state machines, mutual recursion in parsers, certain mathematical sequences.3. Tail RecursionThe recursive call is the last operation in the function. Nothing happens after the recursive call returns — no multiplication, no addition, nothing.// NOT tail recursive — multiplication happens after returnint factorial(int n) { if (n == 1) return 1; return n * factorial(n - 1); // multiply after return — not tail}// Tail recursive — recursive call is the last thingint factorialTail(int n, int accumulator) { if (n == 1) return accumulator; return factorialTail(n - 1, n * accumulator); // last operation}Why does tail recursion matter? In languages that support tail call optimization (like Scala, Kotlin, and many functional languages), tail recursive functions can be converted to iteration internally — no stack frame accumulation, O(1) space. Java does NOT perform tail call optimization, but understanding tail recursion is still important for interviews and functional programming concepts.4. Head RecursionThe recursive call happens first, before any other processing. All processing happens in the return phase.void headRecursion(int n) { if (n == 0) return; headRecursion(n - 1); // call first System.out.println(n); // process after}// Output: 1 2 3 4 5 (processes in reverse order of calls)5. Tree RecursionThe function makes more than one recursive call per invocation. This creates a tree of calls rather than a linear chain. Fibonacci is the classic example.int fibonacci(int n) { if (n <= 1) return n; return fibonacci(n - 1) + fibonacci(n - 2); // TWO recursive calls}The call tree for fibonacci(4): fib(4) / \ fib(3) fib(2) / \ / \ fib(2) fib(1) fib(1) fib(0) / \ fib(1) fib(0)Time Complexity: O(2ⁿ) — exponential! Each call spawns two more. Space Complexity: O(n) — maximum depth of the call treeThis is why memoization (caching results) is so important for tree recursion — it converts O(2ⁿ) to O(n) by never recomputing the same subproblem twice.6. Mutual RecursionA specific form of indirect recursion where two functions call each other alternately to solve a problem. Different from indirect recursion in that the mutual calls are the core mechanism of the solution.// Check if a number is even or odd using mutual recursionboolean isEven(int n) { if (n == 0) return true; return isOdd(n - 1);}boolean isOdd(int n) { if (n == 0) return false; return isEven(n - 1);}Common Recursion Patterns in DSAThese are the patterns you will see over and over in interview problems. Recognizing them is more important than memorizing solutions.Pattern 1: Linear Recursion (Do Something, Recurse on Rest)Process the current element, then recurse on the remaining problem.// Sum of arrayint arraySum(int[] arr, int index) { if (index == arr.length) return 0; // base case return arr[index] + arraySum(arr, index + 1); // current + rest}Pattern 2: Divide and Conquer (Split Into Two Halves)Split the problem into two halves, solve each recursively, combine results.// Merge Sortvoid mergeSort(int[] arr, int left, int right) { if (left >= right) return; // base case — single element int mid = (left + right) / 2; mergeSort(arr, left, mid); // sort left half mergeSort(arr, mid + 1, right); // sort right half merge(arr, left, mid, right); // combine}Pattern 3: Backtracking (Try, Recurse, Undo)Try a choice, recurse to explore it, undo the choice when backtracking.// Generate all subsetsvoid subsets(int[] nums, int index, List<Integer> current, List<List<Integer>> result) { if (index == nums.length) { result.add(new ArrayList<>(current)); return; } // Choice 1: include nums[index] current.add(nums[index]); subsets(nums, index + 1, current, result); current.remove(current.size() - 1); // undo // Choice 2: exclude nums[index] subsets(nums, index + 1, current, result);}Pattern 4: Tree Recursion (Left, Right, Combine)Recurse on left subtree, recurse on right subtree, combine or process results.// Height of binary treeint height(TreeNode root) { if (root == null) return 0; // base case int leftHeight = height(root.left); // solve left int rightHeight = height(root.right); // solve right return 1 + Math.max(leftHeight, rightHeight); // combine}Pattern 5: Memoization (Cache Recursive Results)Store results of recursive calls so the same subproblem is never solved twice.Map<Integer, Integer> memo = new HashMap<>();int fibonacci(int n) { if (n <= 1) return n; if (memo.containsKey(n)) return memo.get(n); // return cached int result = fibonacci(n - 1) + fibonacci(n - 2); memo.put(n, result); // cache before returning return result;}This converts Fibonacci from O(2ⁿ) to O(n) time with O(n) space — a massive improvement.Recursion vs Iteration — When to Use WhichThis is one of the most common interview questions about recursion. Here is a clear breakdown:Use Recursion when:The problem has a naturally recursive structure (trees, graphs, divide and conquer)The solution is significantly cleaner and easier to understand recursivelyThe problem involves exploring multiple paths or choices (backtracking)The depth of recursion is manageable (not too deep to cause stack overflow)Use Iteration when:The problem is linear and a loop is equally clearMemory is a concern (iteration uses O(1) stack space vs O(n) for recursion)Performance is critical and function call overhead mattersJava's stack size limit could be hit (default around 500-1000 frames for deep recursion)The key rule: Every recursive solution can be converted to an iterative one (usually using an explicit stack). But recursive solutions for tree and graph problems are almost always cleaner to write and understand.Time and Space Complexity of Recursive FunctionsAnalyzing complexity for recursive functions requires a specific approach.The Recurrence Relation MethodExpress the time complexity as a recurrence relation and solve it.Factorial:T(n) = T(n-1) + O(1) = T(n-2) + O(1) + O(1) = T(1) + n×O(1) = O(n)Fibonacci (naive):T(n) = T(n-1) + T(n-2) + O(1) ≈ 2×T(n-1) = O(2ⁿ)Binary Search:T(n) = T(n/2) + O(1) = O(log n) [by Master Theorem]Merge Sort:T(n) = 2×T(n/2) + O(n) = O(n log n) [by Master Theorem]Space Complexity Rule for RecursionSpace complexity of a recursive function = maximum depth of the call stack × space per frameLinear recursion (factorial, sum): O(n) spaceBinary recursion (Fibonacci naive): O(n) space (maximum depth, not number of nodes)Divide and conquer (merge sort): O(log n) space (depth of recursion tree)Memoized Fibonacci: O(n) space (memo table + call stack)Classic Recursive Problems With SolutionsProblem 1: Reverse a StringString reverse(String s) { if (s.length() <= 1) return s; // base case // last char + reverse of everything before last char return s.charAt(s.length() - 1) + reverse(s.substring(0, s.length() - 1));}Dry run for "hello":reverse("hello") = 'o' + reverse("hell")reverse("hell") = 'l' + reverse("hel")reverse("hel") = 'l' + reverse("he")reverse("he") = 'e' + reverse("h")reverse("h") = "h"Unwinding: "h" → "he" → "leh" → "lleh" → "olleh" ✅Problem 2: Power Function (x^n)double power(double x, int n) { if (n == 0) return 1; // base case if (n < 0) return 1.0 / power(x, -n); // handle negative if (n % 2 == 0) { double half = power(x, n / 2); return half * half; // x^n = (x^(n/2))^2 } else { return x * power(x, n - 1); }}This is the fast power algorithm — O(log n) time instead of O(n).Problem 3: Fibonacci With Memoizationint[] memo = new int[100];Arrays.fill(memo, -1);int fib(int n) { if (n <= 1) return n; if (memo[n] != -1) return memo[n]; memo[n] = fib(n - 1) + fib(n - 2); return memo[n];}Time: O(n) — each value computed once Space: O(n) — memo array + call stackProblem 4: Tower of HanoiThe classic recursion teaching problem. Move n disks from source to destination using a helper rod.void hanoi(int n, char source, char destination, char helper) { if (n == 1) { System.out.println("Move disk 1 from " + source + " to " + destination); return; } // Move n-1 disks from source to helper hanoi(n - 1, source, helper, destination); // Move the largest disk from source to destination System.out.println("Move disk " + n + " from " + source + " to " + destination); // Move n-1 disks from helper to destination hanoi(n - 1, helper, destination, source);}Time Complexity: O(2ⁿ) — minimum moves required is 2ⁿ - 1 Space Complexity: O(n) — call stack depthProblem 5: Generate All Subsets (Power Set)void generateSubsets(int[] nums, int index, List<Integer> current, List<List<Integer>> result) { result.add(new ArrayList<>(current)); // add current subset for (int i = index; i < nums.length; i++) { current.add(nums[i]); // include generateSubsets(nums, i + 1, current, result); // recurse current.remove(current.size() - 1); // exclude (backtrack) }}For [1, 2, 3] — generates all 8 subsets: [], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]Time: O(2ⁿ) — 2ⁿ subsets Space: O(n) — recursion depthProblem 6: Binary Search Recursivelyint binarySearch(int[] arr, int target, int left, int right) { if (left > right) return -1; // base case — not found int mid = left + (right - left) / 2; if (arr[mid] == target) return mid; else if (arr[mid] < target) return binarySearch(arr, target, mid + 1, right); else return binarySearch(arr, target, left, mid - 1);}Time: O(log n) — halving the search space each time Space: O(log n) — log n frames on the call stackRecursion on Trees — The Natural HabitatTrees are where recursion truly shines. Every tree problem becomes elegant with recursion because a tree is itself a recursive structure — each node's left and right children are trees themselves.// Maximum depth of binary treeint maxDepth(TreeNode root) { if (root == null) return 0; return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));}// Check if tree is symmetricboolean isSymmetric(TreeNode left, TreeNode right) { if (left == null && right == null) return true; if (left == null || right == null) return false; return left.val == right.val && isSymmetric(left.left, right.right) && isSymmetric(left.right, right.left);}// Path sum — does any root-to-leaf path sum to target?boolean hasPathSum(TreeNode root, int target) { if (root == null) return false; if (root.left == null && root.right == null) return root.val == target; return hasPathSum(root.left, target - root.val) || hasPathSum(root.right, target - root.val);}Notice the pattern in all three — base case handles null, recursive case handles left and right subtrees, result combines both.How to Think About Any Recursive Problem — Step by StepThis is the framework you should apply to every new recursive problem you encounter:Step 1 — Identify the base case What is the smallest input where you know the answer directly without any recursion? For arrays it is usually empty array or single element. For trees it is null node. For numbers it is 0 or 1.Step 2 — Trust the recursive call Assume your function already works correctly for smaller inputs. Do not trace through the entire recursion mentally — just trust it. This is the Leap of Faith and it is what makes recursion feel natural.Step 3 — Express the current problem in terms of smaller problems How does the answer for size n relate to the answer for size n-1 (or n/2, or subtrees)? This relationship is your recursive case.Step 4 — Make sure each call moves toward the base case The input must become strictly smaller with each call. If it does not, you have infinite recursion.Step 5 — Write the base case first, then the recursive case Always. Writing the recursive case first leads to bugs because you have not defined when to stop.Common Mistakes and How to Avoid ThemMistake 1: Missing or wrong base case The most common mistake. Missing the base case causes StackOverflowError. Wrong base case causes wrong answers.Always ask — what is the simplest possible input, and what should the function return for it? Write that case first.Mistake 2: Not moving toward the base case If you call factorial(n) inside factorial(n) without reducing n, you loop forever. Every recursive call must make the problem strictly smaller.Mistake 3: Trusting your brain to trace deep recursion Do not try to trace 10 levels of recursion in your head. Trust the recursive call, verify the base case, and check that each call reduces the problem. That is all you need.Mistake 4: Forgetting to return the recursive result// WRONG — result is computed but not returnedint sum(int n) { if (n == 0) return 0; sum(n - 1) + n; // computed but discarded!}// CORRECTint sum(int n) { if (n == 0) return 0; return sum(n - 1) + n;}Mistake 5: Modifying shared state without backtracking In backtracking problems, if you add something to a list before a recursive call, you must remove it after the call returns. Forgetting to backtrack leads to incorrect results and is one of the trickiest bugs to find.Mistake 6: Recomputing the same subproblems Naive Fibonacci computes fib(3) multiple times when computing fib(5). Use memoization whenever you notice overlapping subproblems in your recursion tree.Top LeetCode Problems on RecursionThese are organized by pattern — work through them in this order for maximum learning:Pure Recursion Basics:509. Fibonacci Number — Easy — start here, implement with and without memoization344. Reverse String — Easy — recursion on arrays206. Reverse Linked List — Easy — recursion on linked list50. Pow(x, n) — Medium — fast power with recursionTree Recursion (Most Important):104. Maximum Depth of Binary Tree — Easy — simplest tree recursion112. Path Sum — Easy — decision recursion on tree101. Symmetric Tree — Easy — mutual recursion on tree110. Balanced Binary Tree — Easy — bottom-up recursion236. Lowest Common Ancestor of a Binary Tree — Medium — classic tree recursion124. Binary Tree Maximum Path Sum — Hard — advanced tree recursionDivide and Conquer:148. Sort List — Medium — merge sort on linked list240. Search a 2D Matrix II — Medium — divide and conquerBacktracking:78. Subsets — Medium — generate all subsets46. Permutations — Medium — generate all permutations77. Combinations — Medium — generate combinations79. Word Search — Medium — backtracking on grid51. N-Queens — Hard — classic backtrackingMemoization / Dynamic Programming:70. Climbing Stairs — Easy — Fibonacci variant with memoization322. Coin Change — Medium — recursion with memoization to DP139. Word Break — Medium — memoized recursionRecursion Cheat Sheet// Linear recursion templatereturnType solve(input) { if (baseCase) return directAnswer; // process current return solve(smallerInput);}// Tree recursion templatereturnType solve(TreeNode root) { if (root == null) return baseValue; returnType left = solve(root.left); returnType right = solve(root.right); return combine(left, right, root.val);}// Backtracking templatevoid backtrack(choices, current, result) { if (goalReached) { result.add(copy of current); return; } for (choice : choices) { make(choice); // add to current backtrack(...); // recurse undo(choice); // remove from current }}// Memoization templateMap<Input, Output> memo = new HashMap<>();returnType solve(input) { if (baseCase) return directAnswer; if (memo.containsKey(input)) return memo.get(input); returnType result = solve(smallerInput); memo.put(input, result); return result;}FAQs — People Also AskQ1. What is recursion in Java with a simple example? Recursion is when a function calls itself to solve a smaller version of the same problem. A simple example is factorial — factorial(5) = 5 × factorial(4) = 5 × 4 × factorial(3) and so on until factorial(1) returns 1 directly.Q2. What is the difference between recursion and iteration? Iteration uses loops (for, while) and runs in O(1) space. Recursion uses function calls and uses O(n) stack space for n levels deep. Recursion is often cleaner for tree and graph problems. Iteration is better when memory is a concern or the problem is inherently linear.Q3. What causes StackOverflowError in Java recursion? StackOverflowError happens when recursion goes too deep — too many frames accumulate on the call stack before any of them return. This is caused by missing base case, wrong base case, or input too large for Java's default stack size limit.Q4. What is the difference between recursion and dynamic programming? Recursion solves a problem by breaking it into subproblems. Dynamic programming is recursion plus memoization — storing results of subproblems so they are never computed twice. DP converts exponential recursive solutions into polynomial ones by eliminating redundant computation.Q5. What is tail recursion and does Java support tail call optimization? Tail recursion is when the recursive call is the absolute last operation in the function. Java does NOT support tail call optimization — Java always creates a new stack frame for each call even if it is tail recursive. Languages like Scala and Kotlin (on the JVM) do support it with the tailrec keyword.Q6. How do you convert recursion to iteration? Every recursive solution can be converted to iterative using an explicit stack data structure. The call stack's behavior is replicated manually — push the initial call, loop while stack is not empty, pop, process, and push sub-calls. Tree traversals are a common example of this conversion.ConclusionRecursion is not magic. It is a systematic way of solving problems by expressing them in terms of smaller versions of themselves. Once you internalize the two parts (base case and recursive case), understand the call stack mentally, and learn to trust the recursive call rather than trace it completely, everything clicks.The learning path from here is clear — start with simple problems like Fibonacci and array sum. Move to tree problems where recursion is most natural. Then tackle backtracking. Finally add memoization to bridge into dynamic programming.Every hour you spend understanding recursion deeply pays dividends across the entire rest of your DSA journey. Trees, graphs, divide and conquer, backtracking, dynamic programming — all of them build on this foundation.

RecursionJavaBase CaseCall StackBacktrackingDynamic Programming

LeetCode 784 Letter Case Permutation | Recursion & Backtracking Java Solution

IntroductionThe Letter Case Permutation problem is a classic example of recursion and backtracking, often asked in coding interviews and frequently searched by learners preparing for platforms like LeetCode.This problem helps in understanding:Decision-making at each stepRecursive branchingString manipulationIn this article, we’ll break down the intuition, visualize the decision process using your decision tree, and implement an efficient Java solution.🔗 Problem LinkLeetCode: Letter Case PermutationProblem StatementGiven a string s, you can transform each alphabet character into:LowercaseUppercaseDigits remain unchanged.👉 Return all possible strings formed by these transformations.ExamplesExample 1Input:s = "a1b2"Output:["a1b2","a1B2","A1b2","A1B2"]Example 2Input:s = "3z4"Output:["3z4","3Z4"]Key InsightAt each character:If it's a digit → only one choiceIf it's a letter → two choices:lowercase OR uppercaseSo total combinations:2^(number of letters)Intuition (Using Your Decision Tree)For input: "a1b2"Start from index 0: "" / \ "a" "A" | | "a1" "A1" / \ / \ "a1b" "a1B" "A1b" "A1B" | | | | "a1b2" "a1B2" "A1b2" "A1B2"Understanding the TreeAt 'a' → branch into 'a' and 'A''1' → no branching (digit)'b' → again branching'2' → no branching📌 Leaf nodes = final answersApproach: Recursion + BacktrackingIdeaTraverse the string character by characterIf digit → move forwardIf letter → branch into:lowercaseuppercaseJava Codeimport java.util.*;class Solution { // List to store all results List<String> lis = new ArrayList<>(); public void solve(String s, int ind, String ans) { // Base case: reached end of string if (ind == s.length()) { lis.add(ans); // store generated string return; } char ch = s.charAt(ind); // If character is a digit → only one option if (ch >= '0' && ch <= '9') { solve(s, ind + 1, ans + ch); } else { // Choice 1: convert to lowercase solve(s, ind + 1, ans + Character.toLowerCase(ch)); // Choice 2: convert to uppercase solve(s, ind + 1, ans + Character.toUpperCase(ch)); } } public List<String> letterCasePermutation(String s) { solve(s, 0, ""); // start recursion return lis; }}Step-by-Step ExecutionFor "a1b2":Start → ""'a' → "a", "A"'1' → "a1", "A1"'b' → "a1b", "a1B", "A1b", "A1B"'2' → final stringsComplexity AnalysisTime Complexity: O(2^n)(n = number of letters)Space Complexity: O(2^n)(for storing results)Why This Approach WorksRecursion explores all possibilitiesEach letter creates a branching pointDigits pass through unchangedBacktracking ensures all combinations are generatedKey TakeawaysThis is a binary decision recursion problemLetters → 2 choicesDigits → 1 choiceDecision tree directly maps to recursionPattern similar to:SubsetsPermutations with conditionsWhen This Problem Is AskedCommon in:Coding interviewsRecursion/backtracking roundsString manipulation problemsConclusionThe Letter Case Permutation problem is a perfect example of how recursion can be used to explore all possible combinations efficiently.Once the decision tree is clear, the implementation becomes straightforward. This pattern is widely used in many advanced problems, making it essential to master.Frequently Asked Questions (FAQs)1. Why don’t digits create branches?Because they have only one valid form.2. What is the main concept used?Recursion with decision-making (backtracking).3. Can this be solved iteratively?Yes, using BFS or iterative expansion, but recursion is more intuitive.

LeetCodeMediumJavaRecursion

Fruit Into Baskets – Sliding Window with Two Types

IntroductionLeetCode 904: Fruit Into Baskets is a classic sliding window problem that tests your ability to track a limited number of distinct elements in a subarray.The problem can be rephrased as:Find the longest subarray containing at most 2 distinct types of elements.This is a great example of using HashMap + sliding window to efficiently track counts of elements while expanding and shrinking the window.If you’d like to try solving the problem first, you can attempt it here:Try the problem on LeetCode:https://leetcode.com/problems/fruit-into-baskets/Problem UnderstandingYou are given:An array fruits where fruits[i] represents the type of fruit from tree iTwo baskets, each can hold only one type of fruitRules:Start at any tree and move only to the rightPick exactly one fruit from each tree while movingStop when a tree’s fruit cannot fit in your basketsGoal: Return the maximum number of fruits you can pick.Examples:Input: fruits = [1,2,1]Output: 3Explanation: Pick all fruits [1,2,1].Input: fruits = [0,1,2,2]Output: 3Explanation: Best subarray [1,2,2].Input: fruits = [1,2,3,2,2]Output: 4Explanation: Best subarray [2,3,2,2].A naive approach would check all subarrays, count distinct fruits, and pick the max →Time Complexity: O(n²) → too slow for fruits.length up to 10⁵Key Idea: Sliding Window with At Most Two TypesInstead of brute-force:Track the number of each fruit type in the current window using a HashMapUse two pointers i and j for the windowExpand j by adding fruits[j] to the mapIf the number of distinct types mp.size() exceeds 2:Shrink the window from the left (i) until mp.size() <= 2The window length j - i + 1 gives the max fruits collected so farIntuition:Only two baskets → window can contain at most 2 distinct fruitsThe sliding window efficiently finds the longest subarray with ≤ 2 distinct elementsApproach (Step-by-Step)Initialize i = 0, j = 0 for window pointersInitialize HashMap mp to store fruit countsInitialize co = 0 → maximum fruits collectedIterate j over fruits:Add fruits[j] to the mapCheck mp.size():If ≤ 2 → update co = max(co, j - i + 1)If > 2 → shrink window from i until mp.size() <= 2Continue expanding the windowReturn co as the maximum fruits collectedOptimization:HashMap keeps track of counts → no need to scan subarray repeatedlySliding window ensures linear traversalImplementation (Java)class Solution {public int totalFruit(int[] nums) {HashMap<Integer,Integer> mp = new HashMap<>();int i = 0, j = 0; // window pointersint co = 0; // max fruits collectedwhile (j < nums.length) {// Add current fruit to mapmp.put(nums[j], mp.getOrDefault(nums[j], 0) + 1);if (mp.size() <= 2) {co = Math.max(co, j - i + 1); // valid windowj++;} else {// Shrink window until at most 2 types of fruitswhile (mp.size() > 2) {mp.put(nums[i], mp.get(nums[i]) - 1);if (mp.get(nums[i]) == 0) {mp.remove(nums[i]);}i++;}co = Math.max(co, j - i + 1);j++;}}return co;}}Dry Run ExampleInput:fruits = [1,2,3,2,2]Execution:Window [i, j]Fruit counts mpDistinct TypesValid?Max co[0,0] → [1]{1:1}1Yes1[0,1] → [1,2]{1:1,2:1}2Yes2[0,2] → [1,2,3]{1:1,2:1,3:1}3No → shrink2[1,2] → [2,3]{2:1,3:1}2Yes2[1,3] → [2,3,2]{2:2,3:1}2Yes3[1,4] → [2,3,2,2]{2:3,3:1}2Yes4Output:4Complexity AnalysisTime Complexity: O(n) → Each element is added and removed at most onceSpace Complexity: O(1) → HashMap stores at most 2 types of fruitsEdge Cases ConsideredArray with ≤ 2 types → entire array can be pickedArray with all same type → window length = array lengthZeros or non-continuous fruit types → handled by sliding windowLarge arrays up to 10⁵ elements → O(n) solution works efficientlySliding Window Pattern ImportanceThis problem demonstrates the sliding window + frequency map pattern:Track limited number of distinct elementsExpand/shrink window dynamicallyEfficiently compute max subarray length with constraintsIt’s directly related to problems like:Max consecutive ones with flipsLongest substring with k distinct charactersFruit collection / subarray problems with type limitsConclusionBy tracking fruit counts with a HashMap in a sliding window, we efficiently find the maximum fruits collectible in O(n) time.Mastering this pattern allows solving many array and string problems with constraints on distinct elements in a linear and elegant way.

SlidingWindowHashMapLeetCodeMedium

Stack Data Structure in Java: The Complete In-Depth Guide

1. What Is a Stack?A Stack is a linear data structure that stores elements in a sequential order, but with one strict rule — you can only insert or remove elements from one end, called the top.It is one of the simplest yet most powerful data structures in computer science. Its strength comes from its constraint. Because everything happens at one end, the behavior of a stack is completely predictable.The formal definition: A Stack is a linear data structure that follows the Last In, First Out (LIFO) principle — the element inserted last is the first one to be removed.Here is what a stack looks like visually: ┌──────────┐ │ 50 │ ← TOP (last inserted, first removed) ├──────────┤ │ 40 │ ├──────────┤ │ 30 │ ├──────────┤ │ 20 │ ├──────────┤ │ 10 │ ← BOTTOM (first inserted, last removed) └──────────┘When you push 60 onto this stack, it goes on top. When you pop, 60 comes out first. That is LIFO.2. Real-World AnalogiesBefore writing a single line of code, it helps to see stacks in the real world. These analogies will make the concept permanently stick.A Pile of Plates In a cafeteria, clean plates are stacked on top of each other. You always pick the top plate. You always place a new plate on top. You never reach into the middle. This is a stack.Browser Back Button Every time you visit a new webpage, it gets pushed onto a history stack. When you press the Back button, the browser pops the most recent page off the stack and takes you there. The page you visited first is at the bottom — you only reach it after going back through everything else.Undo Feature in Text Editors When you type in a document and press Ctrl+Z, the most recent action is undone first. That is because every action you perform is pushed onto a stack. Undo simply pops from that stack.Call Stack in Programming When a function calls another function, the current function's state is pushed onto the call stack. When the inner function finishes, it is popped off and execution returns to the outer function. This is the literal stack your programs run on.A Stack of Books Put five books on a table, one on top of another. You can only take the top book without knocking the pile over. That is a stack.3. The LIFO Principle ExplainedLIFO stands for Last In, First Out.It means whatever you put in last is the first thing to come out. This is the exact opposite of a Queue (which is FIFO — First In, First Out).Let us trace through an example step by step:Start: Stack is empty → []Push 10 → [10] (10 is at the top)Push 20 → [10, 20] (20 is at the top)Push 30 → [10, 20, 30] (30 is at the top)Pop → returns 30 (30 was last in, first out) Stack: [10, 20]Pop → returns 20 Stack: [10]Peek → returns 10 (just looks, does not remove) Stack: [10]Pop → returns 10 Stack: [] (stack is now empty)Every single operation happens only at the top. The bottom of the stack is never directly accessible.4. Stack Operations & Time ComplexityA stack supports the following core operations:OperationDescriptionTime Complexitypush(x)Insert element x onto the top of the stackO(1)pop()Remove and return the top elementO(1)peek() / top()Return the top element without removing itO(1)isEmpty()Check if the stack has no elementsO(1)isFull()Check if the stack has reached its capacity (Array only)O(1)size()Return the number of elements in the stackO(1)search(x)Find position of element from top (Java built-in only)O(n)All primary stack operations — push, pop, peek, isEmpty — run in O(1) constant time. This is what makes the stack so efficient. It does not matter whether the stack has 10 elements or 10 million — these operations are always instant.Space complexity for a stack holding n elements is O(n).5. Implementation 1 — Using a Static ArrayThis is the most fundamental way to implement a stack. We use a fixed-size array and a variable called top to track where the top of the stack currently is.How it works:top starts at -1 (stack is empty)On push: increment top, then place the element at arr[top]On pop: return arr[top], then decrement topOn peek: return arr[top] without changing it// StackUsingArray.javapublic class StackUsingArray { private int[] arr; private int top; private int capacity; // Constructor — initialize with a fixed capacity public StackUsingArray(int capacity) { this.capacity = capacity; arr = new int[capacity]; top = -1; } // Push: add element to the top public void push(int value) { if (isFull()) { System.out.println("Stack Overflow! Cannot push " + value); return; } arr[++top] = value; System.out.println("Pushed: " + value); } // Pop: remove and return top element public int pop() { if (isEmpty()) { System.out.println("Stack Underflow! Stack is empty."); return -1; } return arr[top--]; } // Peek: view the top element without removing public int peek() { if (isEmpty()) { System.out.println("Stack is empty."); return -1; } return arr[top]; } // Check if stack is empty public boolean isEmpty() { return top == -1; } // Check if stack is full public boolean isFull() { return top == capacity - 1; } // Return current size public int size() { return top + 1; } // Display all elements public void display() { if (isEmpty()) { System.out.println("Stack is empty."); return; } System.out.print("Stack (top → bottom): "); for (int i = top; i >= 0; i--) { System.out.print(arr[i] + " "); } System.out.println(); } // Main method to test public static void main(String[] args) { StackUsingArray stack = new StackUsingArray(5); stack.push(10); stack.push(20); stack.push(30); stack.push(40); stack.push(50); stack.push(60); // This will trigger Stack Overflow stack.display(); System.out.println("Peek: " + stack.peek()); System.out.println("Pop: " + stack.pop()); System.out.println("Pop: " + stack.pop()); stack.display(); System.out.println("Size: " + stack.size()); }}```**Output:**```Pushed: 10Pushed: 20Pushed: 30Pushed: 40Pushed: 50Stack Overflow! Cannot push 60Stack (top → bottom): 50 40 30 20 10Peek: 50Pop: 50Pop: 40Stack (top → bottom): 30 20 10Size: 3Key Points about Array Implementation:Fixed size — you must declare capacity upfrontVery fast — direct array index accessStack Overflow is possible if capacity is exceededMemory is pre-allocated even if stack is not full6. Implementation 2 — Using an ArrayListAn ArrayList-based stack removes the fixed-size limitation. The ArrayList grows dynamically, so you never have to worry about stack overflow due to capacity.How it works:The end of the ArrayList acts as the topadd() is used for pushremove(size - 1) is used for popget(size - 1) is used for peek// StackUsingArrayList.javaimport java.util.ArrayList;public class StackUsingArrayList { private ArrayList<Integer> list; // Constructor public StackUsingArrayList() { list = new ArrayList<>(); } // Push: add to the end (which is our top) public void push(int value) { list.add(value); System.out.println("Pushed: " + value); } // Pop: remove and return the last element public int pop() { if (isEmpty()) { System.out.println("Stack Underflow! Stack is empty."); return -1; } int top = list.get(list.size() - 1); list.remove(list.size() - 1); return top; } // Peek: view the last element public int peek() { if (isEmpty()) { System.out.println("Stack is empty."); return -1; } return list.get(list.size() - 1); } // Check if stack is empty public boolean isEmpty() { return list.isEmpty(); } // Return size public int size() { return list.size(); } // Display elements from top to bottom public void display() { if (isEmpty()) { System.out.println("Stack is empty."); return; } System.out.print("Stack (top → bottom): "); for (int i = list.size() - 1; i >= 0; i--) { System.out.print(list.get(i) + " "); } System.out.println(); } // Main method to test public static void main(String[] args) { StackUsingArrayList stack = new StackUsingArrayList(); stack.push(5); stack.push(15); stack.push(25); stack.push(35); stack.display(); System.out.println("Peek: " + stack.peek()); System.out.println("Pop: " + stack.pop()); System.out.println("Pop: " + stack.pop()); stack.display(); System.out.println("Is Empty: " + stack.isEmpty()); System.out.println("Size: " + stack.size()); }}```**Output:**```Pushed: 5Pushed: 15Pushed: 25Pushed: 35Stack (top → bottom): 35 25 15 5Peek: 35Pop: 35Pop: 25Stack (top → bottom): 15 5Is Empty: falseSize: 2Key Points about ArrayList Implementation:Dynamic size — grows automatically as neededNo overflow riskSlight overhead compared to raw array due to ArrayList internalsExcellent for most practical use cases7. Implementation 3 — Using a LinkedListA LinkedList-based stack is the most memory-efficient approach when you do not know the stack size in advance. Each element (node) holds data and a pointer to the next node. The head of the LinkedList acts as the top of the stack.How it works:Each node stores a value and a reference to the node below itPush creates a new node and makes it the new headPop removes the head node and returns its valuePeek returns the head node's value without removing it// StackUsingLinkedList.javapublic class StackUsingLinkedList { // Inner Node class private static class Node { int data; Node next; Node(int data) { this.data = data; this.next = null; } } private Node top; // Head of the linked list = top of stack private int size; // Constructor public StackUsingLinkedList() { top = null; size = 0; } // Push: create new node and link it to top public void push(int value) { Node newNode = new Node(value); newNode.next = top; // new node points to current top top = newNode; // new node becomes the new top size++; System.out.println("Pushed: " + value); } // Pop: remove and return top node's data public int pop() { if (isEmpty()) { System.out.println("Stack Underflow! Stack is empty."); return -1; } int value = top.data; top = top.next; // move top pointer to next node size--; return value; } // Peek: return top node's data without removing public int peek() { if (isEmpty()) { System.out.println("Stack is empty."); return -1; } return top.data; } // Check if empty public boolean isEmpty() { return top == null; } // Return size public int size() { return size; } // Display elements from top to bottom public void display() { if (isEmpty()) { System.out.println("Stack is empty."); return; } System.out.print("Stack (top → bottom): "); Node current = top; while (current != null) { System.out.print(current.data + " "); current = current.next; } System.out.println(); } // Main method to test public static void main(String[] args) { StackUsingLinkedList stack = new StackUsingLinkedList(); stack.push(100); stack.push(200); stack.push(300); stack.push(400); stack.display(); System.out.println("Peek: " + stack.peek()); System.out.println("Pop: " + stack.pop()); System.out.println("Pop: " + stack.pop()); stack.display(); System.out.println("Size: " + stack.size()); }}```**Output:**```Pushed: 100Pushed: 200Pushed: 300Pushed: 400Stack (top → bottom): 400 300 200 100Peek: 400Pop: 400Pop: 300Stack (top → bottom): 200 100Size: 2Key Points about LinkedList Implementation:Truly dynamic — each node allocated only when neededNo wasted memory from pre-allocationSlightly more memory per element (each node carries a pointer)Ideal for stacks where size is completely unknown8. Java's Built-in Stack ClassJava provides a ready-made Stack class inside java.util. It extends Vector and is thread-safe by default.// JavaBuiltinStack.javaimport java.util.Stack;public class JavaBuiltinStack { public static void main(String[] args) { Stack<Integer> stack = new Stack<>(); // Push elements stack.push(10); stack.push(20); stack.push(30); stack.push(40); System.out.println("Stack: " + stack); // Peek — look at top without removing System.out.println("Peek: " + stack.peek()); // Pop — remove top System.out.println("Pop: " + stack.pop()); System.out.println("After pop: " + stack); // Search — returns 1-based position from top System.out.println("Search 20: position " + stack.search(20)); // isEmpty System.out.println("Is Empty: " + stack.isEmpty()); // Size System.out.println("Size: " + stack.size()); }}```**Output:**```Stack: [10, 20, 30, 40]Peek: 40Pop: 40After pop: [10, 20, 30]Search 20: position 2Is Empty: falseSize: 3Important Note: In modern Java development, it is often recommended to use Deque (specifically ArrayDeque) instead of Stack for better performance, since Stack is synchronized and carries the overhead of Vector.// Using ArrayDeque as a stack (modern preferred approach)import java.util.ArrayDeque;import java.util.Deque;public class ModernStack { public static void main(String[] args) { Deque<Integer> stack = new ArrayDeque<>(); stack.push(10); // pushes to front stack.push(20); stack.push(30); System.out.println("Top: " + stack.peek()); System.out.println("Pop: " + stack.pop()); System.out.println("Stack: " + stack); }}9. Comparison of All ImplementationsFeatureArrayArrayListLinkedListJava StackArrayDequeSizeFixedDynamicDynamicDynamicDynamicStack Overflow RiskYesNoNoNoNoMemory UsagePre-allocatedAuto-growsPer-node overheadAuto-growsAuto-growsPush TimeO(1)O(1) amortizedO(1)O(1)O(1)Pop TimeO(1)O(1)O(1)O(1)O(1)Peek TimeO(1)O(1)O(1)O(1)O(1)Thread SafeNoNoNoYesNoBest ForKnown size, max speedGeneral useUnknown/huge sizeLegacy codeModern Java10. Advantages & DisadvantagesAdvantagesAdvantageExplanationSimple to implementVery few rules and operations to worry aboutO(1) operationsPush, pop, and peek are all constant timeMemory efficientNo extra pointers needed (array-based)Supports recursionThe call stack is itself a stackEasy undo/redoNatural fit for reversible action trackingBacktrackingPerfectly suited for maze, puzzle, and game solvingExpression evaluationPowers compilers and calculatorsDisadvantagesDisadvantageExplanationLimited accessCannot access elements in the middle directlyFixed size (array)Array-based stacks overflow if size is exceededNo random accessYou cannot do stack[2] — only top is accessibleMemory waste (array)Pre-allocated array wastes space if underusedNot suitable for all problemsMany problems need queues, trees, or graphs insteadStack overflow in recursionVery deep recursion can overflow the JVM call stack11. Real-World Use Cases of StackUnderstanding when to use a stack is just as important as knowing how to implement one. Here is where stacks show up in real software:Function Call Management (Call Stack) Every time your Java program calls a method, the JVM pushes that method's frame onto the call stack. When the method returns, the frame is popped. This is why you see "StackOverflowError" when you write infinite recursion.Undo and Redo Operations Text editors, image editors (Photoshop), and IDEs use two stacks — one for undo history and one for redo history. Every action pushes onto the undo stack. Ctrl+Z pops from it and pushes to the redo stack.Browser Navigation Your browser maintains a back-stack and a forward-stack. Visiting a new page pushes to the back-stack. Pressing Back pops from it and pushes to the forward-stack.Expression Evaluation and Conversion Compilers use stacks to evaluate arithmetic expressions and convert between infix, prefix, and postfix notations. For example: 3 + 4 * 2 must be evaluated considering operator precedence — this is done with a stack.Balanced Parentheses Checking Linters, compilers, and IDEs use stacks to check if brackets are balanced: {[()]} is valid, {[(])} is not.Backtracking Algorithms Maze solving, N-Queens, Sudoku solvers, and depth-first search all use stacks (explicitly or via recursion) to backtrack to previous states when a path fails.Syntax Parsing Compilers parse source code using stacks to match opening and closing constructs like if/else, try/catch, { and }.12. Practice Problems with Full SolutionsHere is where things get really interesting. These problems will sharpen your stack intuition and prepare you for coding interviews.Problem 1 — Reverse a String Using a StackDifficulty: EasyProblem: Write a Java program to reverse a string using a Stack.Approach: Push every character of the string onto a stack, then pop them all. Since LIFO reverses the order, the characters come out reversed.// ReverseString.javaimport java.util.Stack;public class ReverseString { public static String reverse(String str) { Stack<Character> stack = new Stack<>(); // Push all characters for (char c : str.toCharArray()) { stack.push(c); } // Pop all characters to build reversed string StringBuilder reversed = new StringBuilder(); while (!stack.isEmpty()) { reversed.append(stack.pop()); } return reversed.toString(); } public static void main(String[] args) { System.out.println(reverse("hello")); // olleh System.out.println(reverse("java")); // avaj System.out.println(reverse("racecar")); // racecar (palindrome) System.out.println(reverse("datastructure")); // erutcurtasatad }}Problem 2 — Check Balanced ParenthesesDifficulty: Easy–MediumProblem: Given a string containing (, ), {, }, [, ], determine if the brackets are balanced.Approach: Push every opening bracket onto the stack. When you see a closing bracket, check if it matches the top of the stack. If it does, pop. If it does not, the string is unbalanced.// BalancedParentheses.javaimport java.util.Stack;public class BalancedParentheses { public static boolean isBalanced(String expr) { Stack<Character> stack = new Stack<>(); for (char c : expr.toCharArray()) { // Push all opening brackets if (c == '(' || c == '{' || c == '[') { stack.push(c); } // For closing brackets, check the top of stack else if (c == ')' || c == '}' || c == ']') { if (stack.isEmpty()) return false; char top = stack.pop(); if (c == ')' && top != '(') return false; if (c == '}' && top != '{') return false; if (c == ']' && top != '[') return false; } } // Stack must be empty at the end for a balanced expression return stack.isEmpty(); } public static void main(String[] args) { System.out.println(isBalanced("{[()]}")); // true System.out.println(isBalanced("{[(])}")); // false System.out.println(isBalanced("((()))")); // true System.out.println(isBalanced("{]")); // false System.out.println(isBalanced("")); // true (empty is balanced) }}Problem 3 — Reverse a Stack (Without Extra Data Structure)Difficulty: Medium–HardProblem: Reverse all elements of a stack using only recursion — no array or extra stack allowed.Approach: This is a classic recursion problem. You need two recursive functions:insertAtBottom(stack, item) — inserts an element at the very bottom of the stackreverseStack(stack) — pops all elements, reverses, and uses insertAtBottom to rebuild// ReverseStack.javaimport java.util.Stack;public class ReverseStack { // Insert an element at the bottom of the stack public static void insertAtBottom(Stack<Integer> stack, int item) { if (stack.isEmpty()) { stack.push(item); return; } int top = stack.pop(); insertAtBottom(stack, item); stack.push(top); } // Reverse the stack using insertAtBottom public static void reverseStack(Stack<Integer> stack) { if (stack.isEmpty()) return; int top = stack.pop(); reverseStack(stack); // reverse the remaining stack insertAtBottom(stack, top); // insert popped element at bottom } public static void main(String[] args) { Stack<Integer> stack = new Stack<>(); stack.push(1); stack.push(2); stack.push(3); stack.push(4); stack.push(5); System.out.println("Before: " + stack); // [1, 2, 3, 4, 5] reverseStack(stack); System.out.println("After: " + stack); // [5, 4, 3, 2, 1] }}Problem 4 — Evaluate a Postfix ExpressionDifficulty: MediumProblem: Evaluate a postfix (Reverse Polish Notation) expression. Example: "2 3 4 * +" should return 14 because it is 2 + (3 * 4).Approach: Scan left to right. If you see a number, push it. If you see an operator, pop two numbers, apply the operator, and push the result.// PostfixEvaluation.javaimport java.util.Stack;public class PostfixEvaluation { public static int evaluate(String expression) { Stack<Integer> stack = new Stack<>(); String[] tokens = expression.split(" "); for (String token : tokens) { // If it's a number, push it if (token.matches("-?\\d+")) { stack.push(Integer.parseInt(token)); } // If it's an operator, pop two and apply else { int b = stack.pop(); // second operand int a = stack.pop(); // first operand switch (token) { case "+": stack.push(a + b); break; case "-": stack.push(a - b); break; case "*": stack.push(a * b); break; case "/": stack.push(a / b); break; } } } return stack.pop(); } public static void main(String[] args) { System.out.println(evaluate("2 3 4 * +")); // 14 → 2 + (3*4) System.out.println(evaluate("5 1 2 + 4 * + 3 -")); // 14 → 5+((1+2)*4)-3 System.out.println(evaluate("3 4 +")); // 7 }}Problem 5 — Next Greater ElementDifficulty: MediumProblem: For each element in an array, find the next greater element to its right. If none exists, output -1.Example: Input: [4, 5, 2, 10, 8] → Output: [5, 10, 10, -1, -1]Approach: Iterate right to left. Maintain a stack of candidates. For each element, pop all stack elements that are smaller than or equal to it — they can never be the answer for any element to the left. The top of the stack (if not empty) is the next greater element.// NextGreaterElement.javaimport java.util.Stack;import java.util.Arrays;public class NextGreaterElement { public static int[] nextGreater(int[] arr) { int n = arr.length; int[] result = new int[n]; Stack<Integer> stack = new Stack<>(); // stores elements, not indices // Traverse from right to left for (int i = n - 1; i >= 0; i--) { // Pop elements smaller than or equal to current while (!stack.isEmpty() && stack.peek() <= arr[i]) { stack.pop(); } // Next greater element result[i] = stack.isEmpty() ? -1 : stack.peek(); // Push current element for future comparisons stack.push(arr[i]); } return result; } public static void main(String[] args) { int[] arr1 = {4, 5, 2, 10, 8}; System.out.println(Arrays.toString(nextGreater(arr1))); // [5, 10, 10, -1, -1] int[] arr2 = {1, 3, 2, 4}; System.out.println(Arrays.toString(nextGreater(arr2))); // [3, 4, 4, -1] int[] arr3 = {5, 4, 3, 2, 1}; System.out.println(Arrays.toString(nextGreater(arr3))); // [-1, -1, -1, -1, -1] }}Problem 6 — Sort a Stack Using RecursionDifficulty: HardProblem: Sort a stack in ascending order (smallest on top) using only recursion — no loops, no extra data structure.// SortStack.javaimport java.util.Stack;public class SortStack { // Insert element in correct sorted position public static void sortedInsert(Stack<Integer> stack, int item) { if (stack.isEmpty() || item > stack.peek()) { stack.push(item); return; } int top = stack.pop(); sortedInsert(stack, item); stack.push(top); } // Sort the stack public static void sortStack(Stack<Integer> stack) { if (stack.isEmpty()) return; int top = stack.pop(); sortStack(stack); // sort remaining sortedInsert(stack, top); // insert top in sorted position } public static void main(String[] args) { Stack<Integer> stack = new Stack<>(); stack.push(34); stack.push(3); stack.push(31); stack.push(98); stack.push(92); stack.push(23); System.out.println("Before sort: " + stack); sortStack(stack); System.out.println("After sort: " + stack); // smallest on top }}13. Summary & Key TakeawaysA stack is a simple, elegant, and powerful data structure. Here is everything in one place:What it is: A linear data structure that follows LIFO — Last In, First Out.Core operations: push (add to top), pop (remove from top), peek (view top), isEmpty — all in O(1) time.Three ways to implement it in Java:Array-based: fast, fixed size, risk of overflowArrayList-based: dynamic, easy, slightly more overheadLinkedList-based: truly dynamic, memory-efficient per-element, best for unknown sizesWhen to use it:Undo/redo systemsBrowser navigationBalancing brackets and parenthesesEvaluating mathematical expressionsBacktracking problemsManaging recursive function callsDepth-first searchWhen NOT to use it:When you need random access to elementsWhen insertion/deletion is needed from both ends (use Deque)When you need to search efficiently (use HashMap or BST)Modern Java recommendation: Prefer ArrayDeque over the legacy Stack class for non-thread-safe scenarios. Use Stack only when you need synchronized access.The stack is one of those data structures that once you truly understand, you start seeing it everywhere — in your browser, in your IDE, in recursive algorithms, and deep within the operating system itself.This article covered everything from the fundamentals of the Stack data structure to multiple Java implementations, time complexity analysis, real-world applications, and six practice problems of increasing difficulty. Bookmark it as a reference and revisit the practice problems regularly — they are the real test of your understanding.

DataStructuresJavaStackDataStructureLIFO