# 655

#time: O(H * 2**H - 1) need to fill the result array
# space: O(H * 2**H - 1) the number of elements in the result array

from utils.treeNode import TreeNode

class Solution:
    def print(self, root):
        if not root:
            return []
        
        height = self.get_height(root)

        result = [["" for _ in range((2 ** height - 1))] for _ in range(height)]

        self.traverse(root, 0, (2 ** height) - 2, 0, result)

        return result
    
    # DFS traverse
    def traverse(self, root, start, end, level, result):
        if not root:
            return
        
        mid = (start + end) // 2

        result[level][mid] = root.value

        self.traverse(root.left, start, mid - 1, level + 1, result)
        self.traverse(root.right, mid + 1, end, level + 1, result)


    def get_height(self, root):
        if not root:
            return 0
        
        return 1 + max(self.get_height(root.left), self.get_height(root.right))

one = TreeNode(1)
two = TreeNode(2)
three = TreeNode(3)
four = TreeNode(4)
five = TreeNode(5)

one.left = two
two.left = three
three.left = four
one.right = five

print(one)

print('==============')

solution = Solution()
print(solution.print(one))