Simple Java program, with O(height of BST)

  • -2
    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);
            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

    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.