So I was solving this LeetCode question https://leetcode.com/problems/kth-smallest-element-in-a-bst/

The solution for this question is

class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        stack = []
        curr = root

        while stack or curr:
            while curr:
                stack.append(curr)
                curr = curr.left
            curr = stack.pop()
            k -= 1
            if k == 0:
                return curr.val
            curr = curr.right

The one thing I don't understand here is why we using

curr = curr.right

in the last line, what's it's importance?

CodePudding user response：

This solution performs an in-order traversal of the tree. Here are the reasons why that last statement is needed:

• Without it, the only possible navigation would be to go left, as then there is no code that ever visits a right child of a node.

• Without it, the next iteration of the loop would push the same node that was popped from the stack, back on the stack, and after the loop it gets popped again. This means the pop call will always pop the same node. The only possible return value is the node with the least value.

• The meaning of putting a node on the stack is: "we're now going to the left, but please remind me to actually visit this node later, and then move to the right". When a node is popped from the stack, that time has come: we visit it (by reducing the value of k), and then move to the right, so that also that node's right subtree gets visited.