leetcode3-230. Kth Smallest Element in a BST

1. problem

1. Binary Search Tree, left < current < right node
2. find kth smallest value

2. init

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:

3. thought

1. inorder’s self.inorder(root.left, _list) end when we traversal to the most left node.
2. the we append element to List
3. return k-th element

4. trouble

1. stuck in pre/in/post order traversal concept.

5.final solution

Runtime 60 ms Beats 84.60% Memory 18 MB Beats 46.98%

class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        _list = []
        self.inorder(root,_list)
        return _list[k-1]

    def inorder(self, root, _list):
        if root is None: return
        self.inorder(root.left, _list)
        _list.append(root.val)
        self.inorder(root.right, _list)

recursive inorder traversal with early stopping
Runtime 56 ms Beats 89.44% Memory 18 MB Beats 46.98%

class Solution:
    _k = 0
    _list = []
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        self._list = []
        self._k = k
        self.inorder(root)
        return self._list[-1]

    def inorder(self, root):
        if root is None: return
        self.inorder(root.left) # traversal left node
        if len(self._list) == self._k : return # early stopping condition
        self._list.append(root.val) # if no stop, add val into list
        self.inorder(root.right) # traversal right node