Simple Java program, with O(height of BST)


  • -2
    L
    public class Solution {
        public int kthSmallest(TreeNode root, int k) {
            return dfs(root, new ArrayList<Integer>(), k);
        }
        public int dfs(TreeNode root, ArrayList<Integer> list, int k){
            if(root == null)
                return 0;
            int left = dfs(root.left, list, k);
            list.add(root.val);
            if(list.size() == k)       //if the size of list is equal to k, stop BFS, return result
                return list.get(list.size()-1);
            int right = dfs(root.right, list, k);
            
            return (left != 0 ? left : right);    
        }
    }

  • 0
    O

    This is O(k) time complexity rather than O(height)


Log in to reply
 

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