3 ways implemented in JAVA (Python): Binary Search, in-order iterative & recursive


  • 272
    A

    Binary Search (dfs): most preferable

      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);
        }
    

    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);
        }
    

    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
      }
    

    2 yrs later...
    Appreciated everyone reviewing my answers and leaving insightful comments here through the last two years, I've never got chance to reply to all of them, and unfortunately, I no longer write in JAVA and this might be the excuse I won't go back editing my stupid codes any more lol. Below is my Python answer that I just picked up lately, it's more fun and hopefully, easier to understand by its simple structure.

    note: requirement has been changed a bit since last time I visited that the counting could be looked up frequently and BST itself could be altered (inserted/deleted) by multiple times, so that's the main reason that I stored them in an array.

    class Solution(object):
        def kthSmallest(self, root, k):
            """
            :type root: TreeNode
            :type k: int
            :rtype: int
            """
            count = []
            self.helper(root, count)
            return count[k-1]
            
        def helper(self, node, count):
            if not node:
                return
            
            self.helper(node.left, count)
            count.append(node.val)
            self.helper(node.right, count)
    

    Thanks again!


  • 2
    L

    The first one is cool :) But I don't think the third method is BFS, it actually is DFS. And I assume the second one should be in-order traversal of BST.


  • 3
    W

    Thanks a lot! Could you tell me, what is the complexity of the first method?


  • 1
    A

    Yes you are right, the 3rd one is not BFS, it just uses stack. Both 2nd and 3rd are in-order traversal.


  • 7
    A

    The best performance is we just have to count the nodes for once (i.e. kth is root), which is O(n); the worse/average case when we need count nodes for each subtree traversal, binary search is always log(n), and number of traversed subtrees could be n, then as total is O(nlog(n)).


  • 12
    B

    worst case complexity should be O(n^2)? if the tree is not balanced, it can become a linked list with the largest value at root and to the leaf node in decreasing order. And imagine we want k = 1 in this case.


  • 70
    E

    Actually I am wondering why the first method (binary search) is preferable. You need to count the left sub-tree, but why don't we find the kth node directly during the counting, which is exactly in-order DFS?


  • -6
    R

    talk is easy show the code


  • 0
    R

    but time comp is still ON right?


  • 15
    L

    //code is also easy man. Don't be aggressive, we are discussing and learn from each other here.
    public class Solution {

    int count = 0;
    int current = 0;
    public int kthSmallest(TreeNode root, int k) {
        inOrderTraversal(root,k);
        return current;
    }
    public void inOrderTraversal(TreeNode root, int k){
        if(count==k) return;
        else{
            if(root.left!=null) inOrderTraversal(root.left, k);
            if(count==k) return; //break after already found kth smallest.
            count++;
            if(count==k){
                current = root.val;
                return;
            } 
            if(root.right!=null) inOrderTraversal(root.right, k);
        }
    }
    

    }


  • 6
    E

    @ruichang OP shows us 3 possible ways to solve the problem. I was just claiming that the first one is not better than the last two. Please kindly correct me if I was wrong.


  • -1
    R

    I mistake your solution as divide and conquer, sorry


  • 0
    R

    yes but don't you think first one is more clear for divide and conquer thinking, and also needed in interview. Is it still on tim for first solution?


  • 12
    R

    First method is definitely NOT preferred. It has O(N * lg N) average runtime and O(N^2) for worst case;


  • 3
    R

    First method is definitely NOT preferred. It has O(N * lg N) average runtime and O(N^2) for worst case;


  • -2
    R

    how to calculate time complexity?


  • 29
    C

    Actually the first idea is not bad, if we augment the TreeNode data structure, we can get O(h) time solution. Here (http://www.geeksforgeeks.org/find-k-th-smallest-element-in-bst-order-statistics-in-bst/) we can find very detailed description. What angelvivienne did is just implementing "lCount" by using the recursive method.

    Method 2: Augmented Tree Data Structure.

    The idea is to maintain rank of each node. We can keep track of elements in a subtree of any node while building the tree. Since we need K-th smallest element, we can maintain number of elements of left subtree in every node.

    Assume that the root is having N nodes in its left subtree. If K = N + 1, root is K-th node. If K < N, we will continue our search (recursion) for the Kth smallest element in the left subtree of root. If K > N + 1, we continue our search in the right subtree for the (K – N – 1)-th smallest element. Note that we need the count of elements in left subtree only.

    Time complexity: O(h) where h is height of tree.


  • 0
    T

    Yes, I was working on the same lines. I think this is a good solution :)
    I think since a node is visited max. once, the worst time complexity should be O(n) where n is the number of nodes. Please correct me if I'm wrong.
    The only problem I see with this solution is in case global variables are not to be used, which can sometimes be a criterion in interviews.
    Also, this line is not needed, I believe. The check is already performed.:
    if(count==k) return; //break after already found kth smallest.


  • 1
    M

    Not able to understand why this is not working for input [1,null,2], 2

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

  • 0
    L

    Hi, @mahendhar_rao , I guess it's because you used static variable. And [1,null,2], 2 was not the first input for OJ, the static variable was changed in previous test case. Although it's just about the testing mechanism of OJ, it's better not to use static variable like this, it's really not safe.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.