Example: 4 / \ 2 8 / \ 5 10 K = 2, Output = 4
k - 1
. Keep in mind that this is a BST, not just a binary tree.
1. If root
is null
, return null
.
2. Else, if the left node of the root
is not null, find the size of the left subtree. If it's equal to k - 1
, return root
.
3. Else, if k is less than size, recurse through the left subtree. i.e. return findKthSmallest(root.left, k)
4. Recurse through the right subtree, with a new k -> k-leftSize-1 i.e.return findKthSmallest(root.right, k-leftSize-1)
public TreeNode findKthSmallest(TreeNode root, int k) { }
C
Java
Python