class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

class Solution:
    def inorderTraversal(self, root):
        stack = []
        ans = []
        while True:
            while root != None:
                stack.append(root)
                root = root.left
            if not stack:
                return ans
            root = stack.pop()
            ans.append(root.data)
            root = root.right

    def inorderTraversalRecursive(self, root):
        res = []
        self.helper(root, res)
        return res

    def helper(root, ans):
        if not root:
            return
        self.helper(root.left, ans)
        ans.append(root.data)
        self.helper(root.right, ans)


# def inorderTraversal(root):
#     stack = []
#     ans = []
#     while True:
#         while root != None:
#             stack.append(root)
#             root = root.left
#         if not stack:
#             return ans
#         root = stack.pop()
#         ans.append(root.data)
#         root = root.right
#
# def inorderTraversalRecursive(root):
#     res = []
#     helper(root, res)
#     return res
#
# def helper(root, ans):
#     if not root:
#         return
#     helper(root.left, ans)
#     ans.append(root.data)
#     helper(root.right, ans)







def main():
    root = Node(10)
    root.left = Node(9)
    root.right = Node(8)
    root.left.left = Node(7)
    root.left.right = Node(6)
    root.right.left = Node(5)
    print(inorderTraversal(root))
    print(inorderTraversalRecursive(root))
main()