Easy to understand Python solution using in-order traversal

  • 0
    class Solution(object):
        def kthSmallest(self, root, k):
            :type root: TreeNode
            :type k: int
            :rtype: int
            stack = [(root, False)]
            count = 0
            while stack:
                node, flag = stack.pop()
                if node:
                    if flag:
                        count += 1
                        if count == k: return node.val
                        stack.append((node.right, False))
                        stack.append((node, True))
                        stack.append((node.left, False))

    (node, flag) tuple represents the node to visit and whether the node has been visited, and for in-order we go left child first then node then right child.

  • 0

    nice solution! Can you explain the time complexity of this solution?

  • 0

    O(k+log(n)). Since it will:

    1. spend O(log(n)) to find the smallest element, then
    2. spend O(k) to do traversal until the kth element is found

  • 0

    @Kerr.L Got it! Thanks a lot!

Log in to reply

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