Binary Tree: Inorder Traversal

# Definition for a binary tree node.
from typing import List

class TreeNode:
    def __init__(self, x: int) -> None:
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def traversal(self, root: 'TreeNode', out=None) -> List[List[int]]:
        """
                    0
                 /     \    
                1        2
              /   \
            3       4
                  /   \
                6       9

        In-order...: [3, 1, 6, 4, 9, 0, 2]

        T: O(N)
        S: O(N) worst case; O(log N) average
        """

        if out is None:
            out = []

        if not root:
            return []
        
        self.traversal(root.left, out=out)
        out.append(root.val)
        self.traversal(root.right, out=out)

        return out

from collections import deque
class Solution:
    def traversal(self, root: 'TreeNode', out=None)->List[List[int]]:
        """
                    0
                 /     \    
                1        2
              /   \
            3       4
                  /   \
                6       9

        In-order...: [3, 1, 6, 4, 9, 0, 2] 

        T: O(N)
        S: O(N)
        """

        if out is None:
            out = []

        if not root:
            return []

        stack = deque()
        curr = root

        while curr or stack:
            # Traverse down to bottom of the left branch
            while curr:
                stack.append(curr)
                curr = curr.left
            
            # Visit root and then go right
            curr = stack.pop()
            out.append(curr.val)
            curr = curr.right
            
        return out