LeetCode 230 - Find k-th smallest element in BST

Related: Find k-th smallest element in BST
Second largest element in BST
https://leetcode.com/problems/kth-smallest-element-in-a-bst/

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Note: 
You may assume k is always valid, 1 ≤ k ≤ BST's total elements.

Follow up:
What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?

X. DFS

https://discuss.leetcode.com/topic/28910/two-easiest-in-order-traverse-java

The number of nodes (n) in the tree is irrelevant to the complexity. My code inorder traverse the tree and it stops when it finds the Kth node. The time complexity for this code is O(k).

The number of nodes in the tree does change the time complexity. The program actually goes to the left bottom node first and start from there to search for the Kth smallest. Thus the time complexity should be O(log(n) + K). What do you think ?

The time complexity is O(log(n) + K) only if the tree is balanced. In the worst-case scenario the tree can have a height of n, thus the time complexity could be O(n)

public int kthSmallest(TreeNode root, int k) {
    ArrayList<Integer> buffer = new ArrayList<Integer>();
    inorderSearch(root, buffer, k);
    return buffer.get(k-1);
}
public void inorderSearch(TreeNode node, ArrayList<Integer> buffer, int k){
    if(buffer.size() >= k) // break early
        return;
    if(node.left != null){
        inorderSearch(node.left, buffer, k);
    }
    buffer.add(node.val);
    if(node.right != null){
        inorderSearch(node.right, buffer, k);
    }
}

    public int kthSmallest(TreeNode root, int k) {
        
        Stack<TreeNode> stack=new Stack<TreeNode>();
        int c=0;
        TreeNode cur=root;
        while(cur!=null){
            stack.push(cur);
            cur=cur.left;
        }
        while(!stack.isEmpty()){
            TreeNode ptr=stack.pop();
            c++;
            if(c==k)return ptr.val;
            TreeNode rt=ptr.right;
            while(rt!=null){
                stack.push(rt);
                rt=rt.left;
            }
        }
        return 0;
    }

https://discuss.leetcode.com/topic/17810/3-ways-implemented-in-java-python-binary-search-in-order-iterative-recursive

int count = 0;
int result = Integer.MIN_VALUE;

public int kthSmallest(TreeNode root, int k) {
    traverse(root, k);
    return result;
}

public void traverse(TreeNode root, int k) {
    if(root == null) return;
    traverse(root.left, k);
    count ++;
    if(count == k) result = root.val;
    traverse(root.right, k);       
}

https://discuss.leetcode.com/topic/28910/two-easiest-in-order-traverse-java

https://discuss.leetcode.com/topic/17810/3-ways-implemented-in-java-binary-search-in-order-iterative-recursive

DFS in-order recursive:

    // better keep these two variables in a wrapper class
    private static int number = 0;
    private static int count = 0;

    public int kthSmallest(TreeNode root, int k) {
        count = k;
        helper(root);
        return number;
    }
    
    public void helper(TreeNode n) {
        if (n.left != null) helper(n.left);
        count--;
        if (count == 0) {
            number = n.val;
            return;
        }
        if (n.right != null) helper(n.right);
    }

X. DFS in-order iterative:

  public int kthSmallest(TreeNode root, int k) {
        Stack<TreeNode> st = new Stack<>();
        
        while (root != null) {
            st.push(root);
            root = root.left;
        }
            
        while (k != 0) {
            TreeNode n = st.pop();
            k--;
            if (k == 0) return n.val;
            TreeNode right = n.right;
            while (right != null) {
                st.push(right);
                right = right.left;
            }
        }
        
        return -1; // never hit if k is valid
  }

https://discuss.leetcode.com/topic/46008/iterative-in-order-traversal-using-stack-java-solution

As a lot of us know, this question can be solved by in-order traversal. Here, I am going to show how you can solve this question easily by performing iterative in-order traversal using stack.

Code below is the iterative inorder traversal solution. It is pretty straightforward though, so I am not going to explain the code.

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    if(root == null) return list;
    Stack<TreeNode> stack = new Stack<>();
    while(root != null || !stack.empty()){
        while(root != null){
            stack.push(root);
            root = root.left;
        }
        root = stack.pop();
        list.add(root.val);
        root = root.right;
        
    }
    return list;
}

Here, we can solve the finding kth smallest element with as little tweak as possible.

 public int kthSmallest(TreeNode root, int k) {
     Stack<TreeNode> stack = new Stack<>();
     while(root != null || !stack.isEmpty()) {
         while(root != null) {
             stack.push(root);    
             root = root.left;   
         } 
         root = stack.pop();
         if(--k == 0) break;
         root = root.right;
     }
     return root.val;
 }

https://leetcode.com/problems/kth-smallest-element-in-a-bst/discuss/63660/3-ways-implemented-in-JAVA-(Python)%3A-Binary-Search-in-order-iterative-and-recursive

time complexity: O(N) best, O(N^2) worst

public int kthSmallest(TreeNode root, int k) {
      int count = countNodes(root.left);
      if (k <= count) {
          return kthSmallest(root.left, k);
      } else if (k > count + 1) {
          return kthSmallest(root.right, k-1-count); // 1 is counted as current node
      }
      
      return root.val;
  }
  
  public int countNodes(TreeNode n) {
      if (n == null) return 0;
      
      return 1 + countNodes(n.left) + countNodes(n.right);
  }

X. Follow up
https://discuss.leetcode.com/topic/17668/what-if-you-could-modify-the-bst-node-s-structure/2

If we could add a count field in the BST node class, it will take O(n) time when we calculate the count value for the whole tree, but after that, it will take O(logn) time when insert/delete a node or calculate the kth smallest element.

        public int kthSmallest(TreeNode root, int k) {
            TreeNodeWithCount rootWithCount = buildTreeWithCount(root);
            return kthSmallest(rootWithCount, k);
        }
        
        private TreeNodeWithCount buildTreeWithCount(TreeNode root) {
            if (root == null) return null;
            TreeNodeWithCount rootWithCount = new TreeNodeWithCount(root.val);
            rootWithCount.left = buildTreeWithCount(root.left);
            rootWithCount.right = buildTreeWithCount(root.right);
            if (rootWithCount.left != null) rootWithCount.count += rootWithCount.left.count;
            if (rootWithCount.right != null) rootWithCount.count += rootWithCount.right.count;
            return rootWithCount;
        }
        
        private int kthSmallest(TreeNodeWithCount rootWithCount, int k) {
            if (k <= 0 || k > rootWithCount.count) return -1;
            if (rootWithCount.left != null) {
                if (rootWithCount.left.count >= k) return kthSmallest(rootWithCount.left, k);
                if (rootWithCount.left.count == k-1) return rootWithCount.val;
                return kthSmallest(rootWithCount.right, k-1-rootWithCount.left.count);
            } else {
                if (k == 1) return rootWithCount.val;
                return kthSmallest(rootWithCount.right, k-1);
            }
        }
        
        class TreeNodeWithCount {
            int val;
            int count;
            TreeNodeWithCount left;
            TreeNodeWithCount right;
            TreeNodeWithCount(int x) {val = x; count = 1;};
        }

https://discuss.leetcode.com/topic/32792/java-divide-and-conquer-solution-considering-augmenting-tree-structure-for-the-follow-up

http://bookshadow.com/weblog/2015/07/02/leetcode-kth-smallest-element-bst/

Follow up在查询多和更改多的情况下，我们可以为BST的每个节点增加一个int count，然后进行二分查找。

如果BST节点TreeNode的属性可以扩展，则再添加一个属性leftCnt，记录左子树的节点个数

记当前节点为node

当node不为空时循环：

若k == node.leftCnt + 1：则返回node

否则，若k > node.leftCnt：则令k -= node.leftCnt + 1，令node = node.right

否则，node = node.left

上述算法时间复杂度为O(BST的高度)

这题的难点其实在于Follow Up：如果我们频繁的操作该树，并且频繁的调用kth函数，有什么优化方法使时间复杂度降低至O(h)？h是树的高度。根据提示，我们可以在TreeNode中加入一个rank成员，这个变量记录的是该节点的左子树中节点的个数，其实就是有多少个节点比该节点小。这样我们就可以用二叉树搜索的方法来解决这个问题了。这个添加rank的操作可以在建树的时候一起完成。