Monday, July 29, 2019

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.
Example 1:
Input: root = [3,1,4,null,2], k = 1
   3
  / \
 1   4
  \
   2
Output: 1
public int kthSmallest(TreeNode root, int k) {
        ArrayList<Integer> inorderList = inoder(root, new ArrayList<Integer>());
        return inorderList.get(k-1);
    }
    
    private ArrayList<Integer> inoder(TreeNode T, ArrayList<Integer> inorderList) {
        if(T!=null) {
            inoder(T.left, inorderList);
            inorderList.add(T.val);
            inoder(T.right, inorderList);
        }
        return inorderList;
    }

No comments:

Post a Comment