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

class Solution:
    def preorder_traversal(self, node):
        result, rights = [], []

        while node or rights:
            if not node:
                node = rights.pop()
            
            result.append(node.value)

            if node.right:
                rights.append(node.right)
            node = node.left
        
        return result
    
    def preorder_traversal2(self, root):
        result = []
        if not root:
            return result
        
        stack = [root]

        while stack:
            node = stack.pop()
            result.append(node.value)

            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)

        return result 

    def preorder_traversal3(self, node):
        result = []
        self.preorder_traversal_rec(node, result)
        return result
    
    def preorder_traversal_rec(self, node, result):
        if not node:
            return
        
        result.append(node.value)
        self.preorder_traversal_rec(node.left, result)
        self.preorder_traversal_rec(node.right, result)

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