Search Blogs

Showing results for "DFS Traversal"

Found 13 results

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 1306: Jump Game III – Java DFS & Graph Traversal Solution Explained

IntroductionLeetCode 1306 – Jump Game III is an interesting graph traversal problem that combines:Depth First Search (DFS)Breadth First Search (BFS)RecursionVisited trackingCycle detectionAt first glance, this problem looks like an array problem.But internally, it behaves exactly like a graph traversal problem where:Each index acts like a nodeEach jump acts like an edgeThis problem is commonly asked in coding interviews because it tests:Recursive thinkingGraph traversal intuitionAvoiding infinite loopsState trackingProblem Link🔗 https://leetcode.com/problems/jump-game-iii/Problem StatementYou are given:An array arrA starting index startFrom index i, you can jump:i + arr[i]ori - arr[i]Your goal is to determine whether you can reach any index having value:0ExampleInputarr = [4,2,3,0,3,1,2]start = 5OutputtrueExplanationPossible path:5 → 4 → 1 → 3At index:3Value becomes:0So answer is:trueUnderstanding the ProblemThink of every index as a graph node.From each node:index iwe have two possible edges:i + arr[i]andi - arr[i]The goal is simply:Can we reach any node containing value 0?Brute Force IntuitionA naive recursive solution would:Try both forward and backward jumpsContinue recursivelyStop when we find zeroWhy Brute Force FailsWithout tracking visited indices, recursion may enter infinite loops.Example:1 → 3 → 1 → 3 → 1...This creates cycles.So we must track visited nodes.DFS IntuitionWe perform DFS traversal from the starting index.At every index:Check boundariesCheck if already visitedCheck if value is zeroExplore both possible jumpsKey DFS ObservationEach index should only be visited once.Why?Because revisiting creates cycles and unnecessary computation.So we use:HashSet<Integer> visitedorboolean[] visitedRecursive DFS ApproachSteps1. Boundary CheckIf index goes outside array:return false2. Visited CheckIf already visited:return false3. Found ZeroIf current index contains:0Return:true4. Explore Both DirectionsTry:start + arr[start]andstart - arr[start]Java DFS Solutionclass Solution { public boolean solve(HashSet<Integer> zeroIndexes, HashSet<Integer> visited, int start, int[] arr) { if(start >= arr.length || start < 0) return false; if(visited.contains(start)) return false; visited.add(start); if(zeroIndexes.contains(start)) return true; return solve(zeroIndexes, visited, start + arr[start], arr) || solve(zeroIndexes, visited, start - arr[start], arr); } public boolean canReach(int[] arr, int start) { HashSet<Integer> visited = new HashSet<>(); HashSet<Integer> zeroIndexes = new HashSet<>(); for(int i = 0; i < arr.length; i++) { if(arr[i] == 0) { zeroIndexes.add(i); } } return solve(zeroIndexes, visited, start, arr); }}Simpler Optimized DFS SolutionWe actually do not need a separate set for zero indexes.We can directly check:arr[start] == 0Cleaner Java DFS Solutionclass Solution { public boolean dfs(int[] arr, boolean[] visited, int start) { if(start < 0 || start >= arr.length) return false; if(visited[start]) return false; if(arr[start] == 0) return true; visited[start] = true; return dfs(arr, visited, start + arr[start]) || dfs(arr, visited, start - arr[start]); } public boolean canReach(int[] arr, int start) { return dfs(arr, new boolean[arr.length], start); }}Dry RunInputarr = [4,2,3,0,3,1,2]start = 5Step 1Current index:5Value:1Possible jumps:5 + 1 = 65 - 1 = 4Step 2Visit index:4Value:3Possible jumps:4 + 3 = 7 (invalid)4 - 3 = 1Step 3Visit index:1Value:2Possible jumps:1 + 2 = 31 - 2 = -1 (invalid)Step 4Visit index:3Value:0Return:trueBFS ApproachThis problem can also be solved using BFS.Instead of recursion:Use queueExplore neighbors level by levelJava BFS Solutionclass Solution { public boolean canReach(int[] arr, int start) { Queue<Integer> queue = new LinkedList<>(); boolean[] visited = new boolean[arr.length]; queue.offer(start); while(!queue.isEmpty()) { int index = queue.poll(); if(index < 0 || index >= arr.length) continue; if(visited[index]) continue; if(arr[index] == 0) return true; visited[index] = true; queue.offer(index + arr[index]); queue.offer(index - arr[index]); } return false; }}Time Complexity AnalysisDFS ComplexityTime ComplexityO(N)Each index is visited at most once.Space ComplexityO(N)Due to recursion stack and visited array.BFS ComplexityTime ComplexityO(N)Space ComplexityO(N)DFS vs BFSApproachAdvantagesDisadvantagesDFSSimple recursive logicRecursion stackBFSIterative solutionQueue managementInterview ExplanationIn interviews, explain:This problem behaves like graph traversal where each index acts as a node and jumps act as edges. We use DFS or BFS with visited tracking to avoid infinite cycles.This demonstrates strong graph intuition.Common Mistakes1. Forgetting Visited TrackingThis causes infinite recursion.2. Missing Boundary ChecksAlways check:start < 0 || start >= arr.length3. Revisiting NodesAvoid processing already visited indices.FAQsQ1. Is this an array problem or graph problem?Internally it is a graph traversal problem.Q2. Which is better: DFS or BFS?Both are valid.DFS is usually simpler for this problem.Q3. Why do we need visited tracking?To avoid infinite loops caused by cycles.Q4. Can this be solved greedily?No.Because multiple paths must be explored.ConclusionLeetCode 1306 is an excellent beginner-friendly graph traversal problem.It teaches:DFS traversalBFS traversalCycle detectionRecursive thinkingVisited state managementThe most important insight is:Treat every index as a graph node.Once you understand this idea, many graph and traversal interview problems become much easier.

LeetCodeMediumDFSBFSGraph TraversalJavaRecursion

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

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

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

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

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