Python inorder with no extra memory usage (commented and explained)


  • 0
    N
    1. Inorder traversal in a BST iterates on the nodes from the smallest one to the larger one.
    2. From 1, The kth Node that we will reach is the kth Smallest node.
    3. Once we counted k nodes, return the node's value (there's no need to continue the iteration).
    class Solution(object):
        def __init__(self):
            self.count = 0
        def kthSmallest(self, root, k):
            """
            :type root: TreeNode
            :type k: int
            :rtype: int
            """
            return self.inorder(root, k)
    
        def inorder(self, node, k):
            # If we reached a None node, we don't increment the count and 
            # there's no need for more checks
            if node:
    
                left = self.inorder(node.left, k)
                if left is not None:
                    return left
    
                # This part is the same as 'printing' the node in a normal
                # inorder traversal. We return the value only if the current node
                # is the kth node that we passed through. This is the only place
                # that returns a value, which makes the above and below checks work
                self.count += 1
                if self.count == k:
                    return node.val
    
                right = self.inorder(node.right, k)
                if right is not None:
                    return right
    

  • 0

    "no extra memory usage" is not true. Your extra memory usage is proportional to the largest depth encountered up to the kth node.


Log in to reply
 

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