Python solution with detailed explanation


  • 0
    G

    Solution

    Kth Smallest Element in a BST https://leetcode.com/problems/kth-smallest-element-in-a-bst/

    Inorder Traversal

    1. You can do an inorder traversal using recursion or iteration and return the result in O(hleft + k). hleft is required to traverse to extreme left, from there it is O(k). The worst case complexity will be O(2N) or N. For a balanced tree, it should be O(lgN + k).
    class Solution(object):
        def inorder(self, root):
            if root == None:
                return
            self.inorder(root.left)
            self.k = self.k - 1
            if self.k == 0:
                self.ksmall = root.val
                return
            self.inorder(root.right)        
            return
        
        def kthSmallest(self, root, k):
            """
            :type root: TreeNode
            :type k: int
            :rtype: int
            """
            self.k = k
            self.ksmall = None
            self.inorder(root)
            return self.ksmall
    

    Counting Elements Solution

    • The other solution is to count the number of nodes on the left. Then decide whether the root is the kthsmallest or to go to the left or to go to the right. For a tree which is a linked list on the left side and k is 1, we have a N^2 algorithm. For a balanced tree, we have a N/2 + N/4 + ... = O(N).
    class Solution(object):
        def count(self, root):
            if root == None:
                return 0
            return 1 + self.count(root.left) + self.count(root.right)
        
        def kthSmallest(self, root, k):
            """
            :type root: TreeNode
            :type k: int
            :rtype: int
            """
            less_than = self.count(root.left)
            if k == less_than+1:
                return root.val
            elif k <= less_than:
                return self.kthSmallest(root.left, k)
            else:
                return self.kthSmallest(root.right, k-1-less_than)
    

Log in to reply
 

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