230.md

230. Kth Smallest Element in BST

Description

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.

Thinking Process

1. The kth smallest element in BST has (k-1) elements to its left in the tree

Code

public class Solution {
    public int kthSmallest(TreeNode root, int k) {
        int numOfNodesInLeftTree = findNumOfNodes(root.left);
        if(numOfNodesInLeftTree > k - 1){
            return kthSmallest(root.left, k);
        }else if(numOfNodesInLeftTree == k - 1){
            return root.val;
        }else{
            return kthSmallest(root.right, k - numOfNodesInLeftTree - 1);
        }
    }
    
    int findNumOfNodes(TreeNode root){
        if(root == null)
            return 0;
        else
            return findNumOfNodes(root.left) + findNumOfNodes(root.right) + 1;
    }
}