# Binary Tree: Order Level Traversal

from typing import List
from utilities import TreeNode, listToBinaryTree

"""


Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).

Example:
            3
           / \
          9   20
              / \
             15  7

Returns:

[[3], [9, 20], [15, 7]]

Example:
            3
           / \
          9   20
         /    / \
        10   15  7


Returns:

[[3], [9, 20], [10, 15, 7]]


Example:
            3
             \
              4
                \
                 5
                  \
                   6
                    \
                     7
        

Returns:

[[3], [4], [5], [6], [7]]



"""

"""
Understand: 

For each level of the binary tree, append them to a list left to right.

Match:

Definitely a Binary Tree Problem
-> Maybe Breadth-First Search could be useful?

Plan:

Initialize a list of lists
For each "level" of the Binary Tree, iterate through each node and add their value to a list
Append that list to our list of lists
Return the list of lists

Implement:

I think we're done?

Review:

Added some more test cases, feeling pretty good

Evaluate:

Time Complexity
O(n)

Space Complexity

O(n) where n is the number of nodes in the tree

"""

# Solution 1: BFS Recursion
def orderLevelTraversal1(root: TreeNode) -> List[List[int]]:
    levels = []
    appendLevelValues(nodes=[root], levels=levels)
    return levels


def appendLevelValues(nodes: List[TreeNode], levels: List[List[int]]):
    curLevelValues = []
    nextLevelNodes = []

    if not nodes:
        return

    for node in nodes:
        curLevelValues.append(node.val)
        if node.left:
            nextLevelNodes.append(node.left)

        if node.right:
            nextLevelNodes.append(node.right)

    levels.append(curLevelValues)
    appendLevelValues(nextLevelNodes, levels)


# Solution 2: BFS Iterative
def orderLevelTraversal2(root: TreeNode) -> List[List[int]]:
    levels = []
    nodes = [root]
    while nodes:
        # Append to levels list and generate next level of nodes
        curLevelValues = []
        nextLevelNodes = []
        for node in nodes:
            curLevelValues.append(node.val)
            if node.left:
                nextLevelNodes.append(node.left)
            if node.right:
                nextLevelNodes.append(node.right)
        levels.append(curLevelValues)
        nodes = nextLevelNodes
    return levels


# Solution 3: DFS Recursive
def orderLevelTraversal3(root: TreeNode) -> List[List[int]]:
    levels = []
    dfs(root, 0, levels)
    return levels


def dfs(root: TreeNode, curLevel: int, levels: List[List[int]]) -> None:
    if root:
        if curLevel >= len(levels):
            levels.append([])
        levels[curLevel].append(root.val)
        dfs(root.left, curLevel + 1, levels)
        dfs(root.right, curLevel + 1, levels)


# Solution 4 (left to the reader): DFS iterative


def runTests() -> None:
    test_cases = [
        #     3
        #    / \
        #   9   20
        #       / \
        #      15  7
        {
            "input": listToBinaryTree([3, 9, 20, None, None, 15, 7]),
            "expectedOutput": [[3], [9, 20], [15, 7]],
        },
        #     3
        #    / \
        #   9   20
        #  /    / \
        # 10   15  7
        {
            "input": listToBinaryTree([3, 9, 20, 10, None, 15, 7]),
            "expectedOutput": [[3], [9, 20], [10, 15, 7]],
        },
        # 3
        #  \
        #   4
        #     \
        #      5
        #       \
        #        6
        #         \
        #          7
        {
            "input": listToBinaryTree([3, None, 4, None, 5, None, 6, None, 7]),
            "expectedOutput": [[3], [4], [5], [6], [7]],
        },
    ]
    for case in test_cases:
        actual = orderLevelTraversal3(case["input"])
        expected = case["expectedOutput"]

        if actual == expected:
            print("Test success!")
        else:
            print(
                f"""Test failed - {case["input"]} returned {actual}, but expected {expected}"""
            )


if __name__ == "__main__":
    runTests()