My elaboration and sample Python code

  • 0

    For a given node in a BST, you need to know:

    1. values in left subtrees is always smaller than values in the node.

    2. values in right subtrees is always larger than values in the node.

    Therefore, if we use in-order traversal (left->root->right), we can get the sorted ascending node values, and the k-th values would be the answer.

    And, we can get the answer as long as we traverse BST with exactly k nodes through in-order traversal.

    ==> Just utilize variable k to keep track of number of nodes we have traverse. If we find k has subtracted to zero, we just stop traversing the tree and return the value.

    Followings are my sample Python code:

    def kthSmallest(self, root, k):
        return self.helper(root, k)[0]
    def helper(self, node, k):
        val = node.val
        #k-th node is somewhere in the left-subtree
        if node.left:
            val, k = self.helper(node.left, k)
            if k == 0:
                return val, k
        #k-th node is exactly this node
        k -= 1
        if k == 0:
            return node.val, k
        #k-th node is somewhere in the right-subtree
        if node.right:
            val, k = self.helper(node.right, k)
            if k == 0:
                return val, k
        #There would be no more than k nodes under this node, need to further traverse
        return node.val, k

    Since integer is immutable in Python, we can not do "pass by reference" just like in C++.
    Therefore, I need a dummy function helper to return the updated k.

Log in to reply

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