Easy to understand Python solution using in-order traversal


  • 0
    K
    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
                    else:
                        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
    L

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


  • 0
    K

    @leiyama001
    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
    L

    @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.