Python O(n) O(1) solution


  • 0
     def kthSmallest(self, root, k):
            cur = root
            while cur:
                if cur.left:
                    prev = cur.left
                    while prev.right and prev.right != cur:
                        prev = prev.right
                    if not prev.right:
                        prev.right = cur
                        cur = cur.left
                    else:
                        k -= 1
                        if not k:
                            return cur.val
                        cur = prev.right
                        prev.right = None
                        cur = cur.right
                else:
                    k -= 1
                    if not k:
                        return cur.val
                    cur = cur.right

Log in to reply
 

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