Python BST solution


  • 0
    M
        def kthSmallest(self, root, k):
            mid = root
            while True:
                l = mid.left
                r = mid.right
                lCount = self.nodesCount(l)
                rCount = self.nodesCount(r)
                if lCount == k - 1:
                    return mid.val
                if lCount < k - 1:
                    mid = r
                    k = k - lCount - 1
                else:
                    mid = l
            
        def nodesCount(self, node):
            if node is None:
                return 0
            stack = [node]
            count = 1
            while len(stack):
                cur = stack.pop()
                if cur.left:
                    stack.append(cur.left)
                    count += 1
                if cur.right:
                    stack.append(cur.right)
                    count += 1
            return count
    

  • 0
    D

    @mpan753 said in Python BST solution:

    def kthSmallest(self, root, k):
    mid = root
    while True:
    l = mid.left
    r = mid.right
    lCount = self.nodesCount(l)
    rCount = self.nodesCount(r)
    if lCount == k - 1:
    return mid.val
    if lCount < k - 1:
    mid = r
    k = k - lCount - 1
    else:
    mid = l

    def nodesCount(self, node):
        if node is None:
            return 0
        stack = [node]
        count = 1
        while len(stack):
            cur = stack.pop()
            if cur.left:
                stack.append(cur.left)
                count += 1
            if cur.right:
                stack.append(cur.right)
                count += 1
        return count
    

    nice solution. I never thought of doing binary search using node count in a tree however this solution is just 30% better than other solutions. Whereas simple inorder traversal makes the solution 91% better.

    class Solution(object):
        count = 0
        result = None
        def kthSmallestUtil(self, root, k):
            if root is None:
                return
            if self.result is not None:
                return self.result
    
            self.kthSmallestUtil(root.left, k)
            self.count = self.count + 1
            if (self.count == k):
                self.result = root.val
                return root.val
            self.kthSmallestUtil(root.right, k)
    
        def kthSmallest(self, root, k):
            """
            :type root: TreeNode
            :type k: int
            :rtype: int
            """
            self.kthSmallestUtil(root, k)
            return self.result
    

Log in to reply
 

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