✅BEATS 100% | DFS | JAVA | EXPLAINED🔥🔥🔥
Approach:\nEmploys an in-order traversal, which visits nodes in ascending order for BSTs.\nA global variable count keeps track of the number of nodes visited.\n
**Approach:**\nEmploys an in-order traversal, which visits nodes in ascending order for BSTs.\nA global variable count keeps track of the number of nodes visited.\nThe inOrder function:\n\n**Base case:** If the root is null, return.\n\nRecursively traverse the left subtree.\nIncrement count.\nIf count equals k, update the ans array with the current node\'s value and return.\nRecursively traverse the right subtree.\n\n**Time Complexity: O(n)**\nThe code visits each node of the tree once, resulting in linear time complexity with respect to the number of nodes (n).\n\n**Space Complexity: O(h)**\nThe space complexity is determined by the maximum depth of the tree (h). In the worst case (a skewed tree), the recursion stack can reach a depth of h, leading to O(h) space usage.\n\n**Explanation:**\nThe code effectively leverages in-order traversal to find the kth smallest element. The global count variable keeps track of the number of nodes visited, allowing the code to stop when the kth node is reached. The inOrder function recursively traverses the tree, updating count and storing the kth smallest element in the ans array.\n\n# Code\n```java []\n/**\n * Definition for a binary tree node.\n * public class TreeNode {\n *     int val;\n *     TreeNode left;\n *     TreeNode right;\n *     TreeNode() {}\n *     TreeNode(int val) { this.val = val; }\n *     TreeNode(int val, TreeNode left, TreeNode right) {\n *         this.val = val;\n *         this.left = left;\n *         this.right = right;\n *     }\n * }\n */\n // \n\n // Using inorder taversal, the property of inorder is it will traverse in a way which will be in asc order of elements\n // so travel k times from extreme left with inroder traversal to get the kth smallest\nclass Solution {\n    int count =0;\n    public int kthSmallest(TreeNode root, int k) {\n        int[] ans= new int[1];\n        inOrder(root, k, ans );\n        return ans[0];\n    }\n\n   public void inOrder(TreeNode root, int k, int[] ans){\n       if(root==null){\n           return;\n       }\n       inOrder(root.left,k, ans);\n       count++;\n       if(k==count){\n           ans[0]=root.val;\n           return;\n        }\n       inOrder(root.right,k, ans);\n   }\n}\n```
['Java']