Search Blogs

Showing results for "Binary Tree Inorder Traversal"

Found 8 results

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

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

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