Easy to understand JAVA solution


  • 3
    4
    public class Solution {
        public int kthSmallest(TreeNode root, int k) {
            int leftNum = countNodes(root.left);
            
            if (leftNum + 1 == k)
                return root.val;
            else if (leftNum  + 1 > k) {
                return kthSmallest(root.left, k);
            }
            else
                return kthSmallest(root.right, k - leftNum - 1);
        }
        
        private int countNodes(TreeNode root) {
            if (root == null)
                return 0;
            
            return 1 + countNodes(root.left) + countNodes(root.right);
        }
    }
    

    The idea is to determine where the target falls (left side, the root, or the right side) at each level.


  • 0
    Z

    Nice solution! What is the worst case time complexity of your method? Still O(n)?


  • 0
    W

    This solution is much better than taking the whole in-order traversal. Asymptotically, if the tree is balanced, since countNodes is doing n/2 work, time complexity is still O(n) and not O(height)


  • 5
    X

    I think the time complexity will be huge for this solution. Count Nodes get called many times, right?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.