from utils.treeNode import TreeNode
from utils.treeUtils import generate_tree

class Solution:
    def in_order_traversal(self, node):
        result = []
        self.in_order_rec(node, result)
        return result
    
    def in_order_rec(self, node, result):
        if not node:
            return
        
        self.in_order_rec(node.left, result)

        result.append(node.value)

        self.in_order_rec(node.right, result)

    def in_order_traversal2(self, node):
        result = []
        if not node:
            return result
        
        stack = []
        while node or stack:
            if node:
                stack.append(node)
                node = node.left
                continue
            
            node = stack.pop()
            result.append(node.value)
            node = node.right
        
        return result

    def in_order_traversal3(self, node):
        stack, result = [], []
        while node:
            stack.append(node)
            node = node.left
        
        while stack:
            node = stack.pop()
            result.append(node.value)

            if node.right:
                node = node.right
                while node:
                    stack.append(node)
                    node = node.left
        
        return result



root = generate_tree()
print(root)
solution = Solution()
print(solution.in_order_traversal3(root))