0

I am solving this problem from leetcode and wrote some code on my own for it. I followed the idea mentioned here: find-kth-smallest-element-in-a-binary-search-tree-in-optimum-way

Looks like it doesn't return the correct result and I needed some feedback on what could be wrong with this logic. Can anyone please provide some insight here? If possible, try to explain your answer with the same approach I am using so it would be easier to understand where I am going wrong. Thanks!

Here is my code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int kthSmallest(TreeNode root, int k) {
        //what happens if root == null
        //what happens if k > total size of tree
        return kthSmallestNode(root,k).val;

    }

    public static TreeNode kthSmallestNode(TreeNode root,int k){
        if(root==null) return root;
        int numberOfNodes = countNodes(root.left);

        if(k == numberOfNodes ) return root;
        if(k<numberOfNodes ) return kthSmallestNode(root.left,k);
        else return kthSmallestNode(root.right,k-numberOfNodes );
    } 

    private static int countNodes(TreeNode node){
        if(node == null) return 0;
        else return 1+countNodes(node.left)+countNodes(node.right);
    }
}

Custom Testcase:

TreeNode - [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20] 
k = 3

My Answer - 8
Expected Answer - 17 (This is as per leetcode)
Community
  • 1
  • 1
Rohan Dalvi
  • 1,215
  • 1
  • 16
  • 38
  • "it doesn't return the correct result" -- What does it return? Looking at a [MCVE](http://stackoverflow.com/help/mcve) would be a lot better than just eyeballing the code. – azurefrog Apr 07 '16 at 18:25
  • That being said, your `maxDepth()` method is returning an element count, not a depth. – azurefrog Apr 07 '16 at 18:27
  • sorry yes, I forgot to rename the function. I will make the change – Rohan Dalvi Apr 07 '16 at 18:28
  • 2
    Are you sure your tree is well-formed? The code you've posted here looks correct, so you might want to debug in and validate the tree's structure. – azurefrog Apr 07 '16 at 18:48

0 Answers0