# DFS
#   - Time complexity: O(n)
#   - Space complexity: O(n)
    def isValidBST(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: bool
        """
        res = [True]

        def dfs(node, minLimit, maxLimit):
            if not res[0]:
                return
            if not node:
                return

            if not minLimit < node.val < maxLimit:
                res[0] = False
                return
            dfs(node.left, minLimit, node.val)
            dfs(node.right, node.val, maxLimit)

        dfs(root, float('-inf'), float('inf'))
        return res[0]
# BFS      
#   - Time complexity: O(n)
#   - Space complexity: O(n)
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True

        q = deque([(root, float("-inf"), float("inf"))])

        while q:
            node, left, right = q.popleft()
            if not (left < node.val < right):
                return False
            if node.left:
                q.append((node.left, left, node.val))
            if node.right:
                q.append((node.right, node.val, right))

        return True      

# binary seach
#  - time: O(h) # Where h is the height of the tree.
#  - space: O(1)
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        n = root
        while True:
            if p.val < n.val < q.val or q.val < n.val < p.val:  # 如果 n 的值介于 p 和 q 的值之间，则 n 为其 LCA
                return n
            elif p.val < n.val and q.val < n.val:  # 如果 p 和 q 的值都小于 n 的值，则 p 和 q 的LCA一定在左子树（因为题目保证p和q都一定存在）
                n = n.left
            elif p.val > n.val and q.val > n.val:  # 如果 p 和 q 的值都大于 n 的值，则 p 和 q 的LCA一定在左右树（因为题目保证p和q都一定存在）
                n = n.right
            elif (n.val == p.val or
                  q.val == n.val):  # 如果遇到一个节点的值等于 p 或 q，再往下面搜索，不可能找到 common ancestor（因为下面的节点不可能是当前节点的ancestor），所以只能取当前节点
                return n

# DFS (Inorder Traversal)
#  - time: O(n) 
#  - space: O(n) # O(2n)
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        arr = []

        def dfs(node):
            if not node:
                return
            
            dfs(node.left)
            arr.append(node.val)
            dfs(node.right)
        
        dfs(root)
        return arr[k - 1]
      
# DFS (Recursive)
#  - time: O(n) 
#  - space: O(n)
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        cnt = k
        res = root.val

        def dfs(node):
            nonlocal cnt, res
            if not node:
                return
            
            dfs(node.left)
            cnt -= 1
            if cnt == 0:
                res = node.val
                return
            dfs(node.right)
        
        dfs(root)
        return res

# DFS (Iterative)
#  - time: O(n) 
#  - space: O(n)
#  - DFS 的终止条件：尽可能地往左下走，直到没有元素，此时
        stack = []
        cur = root  # cur 指向当前要被扫描的节点
        while cur or stack:  # 只有当前指向的节点为 None 且之前放进 stack 的节点都被处理
            while cur:  # 一直向左下找节点，直到其左下无节点了
                stack.append(cur)  # 之后要处理当前的中间节点，所以需要把中间节点存入 stack
                cur = cur.left
            cur = stack.pop(-1)  # 当前最左下元素为空后，从 stack 中找到中序节点，处理它。之后再处理其右子树

            k -= 1
            if k == 0:
                return cur.val
            cur = cur.right
            
            
# BFS
	def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
		stack = [root]
		cur = root
		while cur or stack:
			while cur:
				stack.append(cur)
				cur = cur.left

			n = stack.pop(-1)
			if k == 1:
				return n.val
			k -= 1

			cur = n.right