Tree Traversal

#Topic: Tree Node Class and Tree Creation
#Time: O(n) — proportional to the number of nodes n
#Space: O(n) — stores all nodes

from __future__ import annotations
from collections import deque


class TreeNode:
    """Binary tree node."""

    def __init__(
        self,
        val: int = 0,
        left: TreeNode | None = None,
        right: TreeNode | None = None,
    ) -> None:
        self.val = val
        self.left = left
        self.right = right

    def __repr__(self) -> str:
        return f"TreeNode({self.val})"


def build_tree_from_list(values: list[int | None]) -> TreeNode | None:
    """Create a binary tree from a level-order list.

    Args:
        values: List of node values in level order (None = empty spot)

    Returns:
        Root node of the tree

    Time:  O(n)
    Space: O(n)"""
    if not values or values[0] is None:
        return None

    root = TreeNode(values[0])
    queue: deque[TreeNode] = deque([root])
    i = 1

    while queue and i < len(values):
        node = queue.popleft()

        #Left child
        if i < len(values) and values[i] is not None:
            node.left = TreeNode(values[i])
            queue.append(node.left)
        i += 1

        #Right child
        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i])
            queue.append(node.right)
        i += 1

    return root


def tree_height(root: TreeNode | None) -> int:
    """Height of the tree (maximum number of edges from root to leaf).

    Time:  O(n)
    Space: O(h)"""
    if root is None:
        return -1  #Empty tree height = -1
    return 1 + max(tree_height(root.left), tree_height(root.right))


def count_nodes(root: TreeNode | None) -> int:
    """Number of nodes in the tree.

    Time:  O(n)
    Space: O(h)"""
    if root is None:
        return 0
    return 1 + count_nodes(root.left) + count_nodes(root.right)


def print_tree(root: TreeNode | None, level: int = 0, prefix: str = "Root:") -> None:
    """Print the tree as ASCII art.

    Time:  O(n)
    Space: O(h)"""
    if root is None:
        return
    print(" " * (level * 4) + prefix + str(root.val))
    if root.left or root.right:
        if root.left:
            print_tree(root.left, level + 1, "L── ")
        else:
            print(" " * ((level + 1) * 4) + "L── (None)")
        if root.right:
            print_tree(root.right, level + 1, "R── ")
        else:
            print(" " * ((level + 1) * 4) + "R── (None)")


#── Example Execution ──────────────────────────────────────────────────────────────
if __name__ == "__main__":
    #       1
    #      / \
    #     2   3
    #    / \ / \
    #   4  5 6  7
    values = [1, 2, 3, 4, 5, 6, 7]
    root = build_tree_from_list(values)

    print("=== Tree Structure ===")
    print_tree(root)

    print(f"\nTree Height: {tree_height(root)}")
    print(f"Number of Nodes:   {count_nodes(root)}")

    #Asymmetric Tree Test
    print("\n=== Asymmetric Tree ===")
    asym = build_tree_from_list([1, 2, 3, None, 4, None, 5])
    print_tree(asym)
    print(f"Height: {tree_height(asym)}, Number of Nodes: {count_nodes(asym)}")

#Topic: Tree Traversal — Recursive Method (Pre-order/In-order/Post-order)
#Time: O(n) — Each node visited exactly once
#Space: O(h) — Recursion call stack depth = Tree height

from __future__ import annotations
import sys

sys.setrecursionlimit(10_000)

from collections import deque


class TreeNode:
    def __init__(self, val: int = 0,
                 left: "TreeNode | None" = None,
                 right: "TreeNode | None" = None) -> None:
        self.val = val
        self.left = left
        self.right = right


#── Recursive Traversal ──────────────────────────────────────────────────────────────

def preorder(root: TreeNode | None) -> list[int]:
    """Preorder traversal: Current → Left → Right.

    Uses: Tree copy, serialization, print
    Time:  O(n)
    Space: O(h)"""
    if root is None:
        return []
    return [root.val] + preorder(root.left) + preorder(root.right)


def inorder(root: TreeNode | None) -> list[int]:
    """Inorder traversal: Left → Current → Right.

    Uses: Ascending output in BST, expression tree evaluation
    Time:  O(n)
    Space: O(h)"""
    if root is None:
        return []
    return inorder(root.left) + [root.val] + inorder(root.right)


def postorder(root: TreeNode | None) -> list[int]:
    """Postorder traversal: Left → Right → Current.

    Uses: Tree deletion, folder size calculation, expression computation
    Time:  O(n)
    Space: O(h)"""
    if root is None:
        return []
    return postorder(root.left) + postorder(root.right) + [root.val]


#── In-place (passing result list as argument) version — Memory efficient ────────────────

def preorder_inplace(root: TreeNode | None, result: list[int]) -> None:
    """In-place preorder traversal (without creating a new list).

    Time:  O(n)
    Space: O(h)"""
    if root is None:
        return
    result.append(root.val)
    preorder_inplace(root.left, result)
    preorder_inplace(root.right, result)


def inorder_inplace(root: TreeNode | None, result: list[int]) -> None:
    """In-place inorder traversal."""
    if root is None:
        return
    inorder_inplace(root.left, result)
    result.append(root.val)
    inorder_inplace(root.right, result)


def postorder_inplace(root: TreeNode | None, result: list[int]) -> None:
    """In-place postorder traversal."""
    if root is None:
        return
    postorder_inplace(root.left, result)
    postorder_inplace(root.right, result)
    result.append(root.val)


#── Helper: Create tree from list ─────────────────────────────────────────────────────

def build(values: list[int | None]) -> TreeNode | None:
    if not values or values[0] is None:
        return None
    root = TreeNode(values[0])
    q: deque[TreeNode] = deque([root])
    i = 1
    while q and i < len(values):
        node = q.popleft()
        if i < len(values) and values[i] is not None:
            node.left = TreeNode(values[i])
            q.append(node.left)
        i += 1
        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i])
            q.append(node.right)
        i += 1
    return root


#── Example Execution ──────────────────────────────────────────────────────────────
if __name__ == "__main__":
    #       1
    #      / \
    #     2   3
    #    / \ / \
    #   4  5 6  7
    root = build([1, 2, 3, 4, 5, 6, 7])

    print("=== Recursive Traversal Results ===")
    print(f"Pre-order:   {preorder(root)}")
    print(f"In-order:    {inorder(root)}")
    print(f"Post-order:  {postorder(root)}")

    print("=== In-place Traversal ===")
    res_pre: list[int] = []
    res_in: list[int] = []
    res_post: list[int] = []
    preorder_inplace(root, res_pre)
    inorder_inplace(root, res_in)
    postorder_inplace(root, res_post)
    print(f"Pre-order: {res_pre}")
    print(f"In-order: {res_in}")
    print(f"Post-order: {res_post}")

    #In BST, In-order = Sorted
    print("=== BST In-order Traversal = Sorted ===")
    #      4
    #     / \
    #    2   6
    #   / \ / \
    #  1  3 5  7
    bst = build([4, 2, 6, 1, 3, 5, 7])
    print(f"BST In-order Traversal: {inorder(bst)}  ← Ascending!")

#Topic: Tree Traversal — Iterative (Stack) Method (Pre-order/In-order/Post-order)
#Time: O(n) — Each node visited exactly once
#Space: O(h) — Explicit stack size = tree height

from __future__ import annotations
from collections import deque


class TreeNode:
    def __init__(self, val: int = 0,
                 left: "TreeNode | None" = None,
                 right: "TreeNode | None" = None) -> None:
        self.val = val
        self.left = left
        self.right = right


#── Iterative Traversal ──────────────────────────────────────────────────────────────

def preorder_iterative(root: TreeNode | None) -> list[int]:
    """Iterative Preorder Traversal: Current → Left → Right.

    Key Idea:
      - Start by putting the root in the stack
      - pop → visit → push right → push left
      - Push left later so it's processed first (LIFO)

    Time:  O(n)
    Space: O(h)"""
    if root is None:
        return []

    result: list[int] = []
    stack: list[TreeNode] = [root]

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

        #Push right first → left is popped first
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)

    return result


def inorder_iterative(root: TreeNode | None) -> list[int]:
    """Iterative Inorder Traversal: Left → Current → Right.

    Key Idea:
      - Move to the leftmost node using a curr pointer while pushing onto the stack
      - Reach the leftmost → pop → visit → curr = curr.right
      - Repeat for the right subtree

    Time:  O(n)
    Space: O(h)"""
    result: list[int] = []
    stack: list[TreeNode] = []
    curr: TreeNode | None = root

    while curr or stack:
        #Move to the far left
        while curr:
            stack.append(curr)
            curr = curr.left

        #Visit and move right
        curr = stack.pop()
        result.append(curr.val)
        curr = curr.right

    return result


def postorder_iterative(root: TreeNode | None) -> list[int]:
    """Iterative Postorder Traversal: Left → Right → Current.

    Key Idea (Using Reverse):
      - Reverse a preorder traversal (Current→Right→Left) to get postorder
      - That is, pop from stack → add to result → push left → push right
      - Reverse the result at the end

    Time:  O(n)
    Space: O(h)"""
    if root is None:
        return []

    result: list[int] = []
    stack: list[TreeNode] = [root]

    while stack:
        node = stack.pop()
        result.append(node.val)   #Current visit (reverse at the end since it's in reverse order)

        if node.left:             #Push left first (right is popped first)
            stack.append(node.left)
        if node.right:
            stack.append(node.right)

    result.reverse()              #Current → Right → Left → Reverse → Left → Right → Current
    return result


def postorder_two_stack(root: TreeNode | None) -> list[int]:
    """Postorder Traversal Using Two Stacks (For Educational Purpose).

    Time:  O(n)
    Space: O(n) — the second stack can store up to n elements"""
    if root is None:
        return []

    stack1: list[TreeNode] = [root]
    stack2: list[int] = []

    while stack1:
        node = stack1.pop()
        stack2.append(node.val)

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

    return stack2[::-1]


#── Helper: Create tree from list ─────────────────────────────────────────────────────

def build(values: list[int | None]) -> TreeNode | None:
    if not values or values[0] is None:
        return None
    root = TreeNode(values[0])
    q: deque[TreeNode] = deque([root])
    i = 1
    while q and i < len(values):
        node = q.popleft()
        if i < len(values) and values[i] is not None:
            node.left = TreeNode(values[i])
            q.append(node.left)
        i += 1
        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i])
            q.append(node.right)
        i += 1
    return root


#── Example Execution ──────────────────────────────────────────────────────────────
if __name__ == "__main__":
    #       1
    #      / \
    #     2   3
    #    / \ / \
    #   4  5 6  7
    root = build([1, 2, 3, 4, 5, 6, 7])

    print("=== Iterative (Stack) Traversal Results ===")
    print(f"Pre-order:   {preorder_iterative(root)}")
    print(f"In-order:    {inorder_iterative(root)}")
    print(f"Post-order:  {postorder_iterative(root)}")
    print(f"Post-order (Two Stacks):     {postorder_two_stack(root)}")

    print("\n=== Recursive vs Iterative Result Comparison ===")
    from src.02_recursive_traversal import preorder, inorder, postorder  # noqa

    #Direct comparison (should be the same)
    assert preorder_iterative(root) == [1, 2, 4, 5, 3, 6, 7]
    assert inorder_iterative(root) == [4, 2, 5, 1, 6, 3, 7]
    assert postorder_iterative(root) == [4, 5, 2, 6, 7, 3, 1]
    print("All results match ✓")

    #Skewed tree (left-only)
    print("\n=== Skewed Tree ===")
    #  1
    #   \
    #    2
    #     \
    #      3
    skewed = build([1, None, 2, None, None, None, 3])
    #Direct construction
    skewed = TreeNode(1)
    skewed.right = TreeNode(2)
    skewed.right.right = TreeNode(3)
    print(f"In-order (right-skewed): {inorder_iterative(skewed)}")

#Topic: Level Order Traversal (BFS), Grouping by Level, Zigzag Traversal
#Time: O(n) — Each node visited exactly once
#Space: O(w) — w = maximum width (in a complete binary tree w ≈ n/2)

from __future__ import annotations
from collections import deque


class TreeNode:
    def __init__(self, val: int = 0,
                 left: "TreeNode | None" = None,
                 right: "TreeNode | None" = None) -> None:
        self.val = val
        self.left = left
        self.right = right


def level_order(root: TreeNode | None) -> list[int]:
    """Basic Level Order Traversal (BFS).

    Time:  O(n)
    Space: O(w) — max size of queue = maximum width"""
    if root is None:
        return []

    result: list[int] = []
    queue: deque[TreeNode] = deque([root])

    while queue:
        node = queue.popleft()
        result.append(node.val)

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

    return result


def level_order_by_levels(root: TreeNode | None) -> list[list[int]]:
    """Level-wise Grouping BFS.

    Key: Fix the current level size with len(queue) at the start of the loop

    Time:  O(n)
    Space: O(w)"""
    if root is None:
        return []

    result: list[list[int]] = []
    queue: deque[TreeNode] = deque([root])

    while queue:
        level_size = len(queue)   #Current number of nodes at the level (important!)
        level: list[int] = []

        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)

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

        result.append(level)

    return result


def zigzag_level_order(root: TreeNode | None) -> list[list[int]]:
    """Zigzag (Spiral) Level Order Traversal.

    Even levels: left → right (forward)
    Odd levels: right → left (reverse)

    Time:  O(n)
    Space: O(w)"""
    if root is None:
        return []

    result: list[list[int]] = []
    queue: deque[TreeNode] = deque([root])
    left_to_right = True   #First level is forward

    while queue:
        level_size = len(queue)
        level: list[int] = []

        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)

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

        if not left_to_right:
            level.reverse()   #Reverse level is reversed

        result.append(level)
        left_to_right = not left_to_right   #Change of direction

    return result


def right_side_view(root: TreeNode | None) -> list[int]:
    """Nodes visible from the right (last node of each level).

    Time:  O(n)
    Space: O(w)"""
    if root is None:
        return []

    result: list[int] = []
    queue: deque[TreeNode] = deque([root])

    while queue:
        level_size = len(queue)

        for i in range(level_size):
            node = queue.popleft()

            if i == level_size - 1:   #Last node of the level
                result.append(node.val)

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

    return result


def max_depth_bfs(root: TreeNode | None) -> int:
    """Find Maximum Depth of Tree using BFS.

    Time:  O(n)
    Space: O(w)"""
    if root is None:
        return 0

    depth = 0
    queue: deque[TreeNode] = deque([root])

    while queue:
        depth += 1
        for _ in range(len(queue)):
            node = queue.popleft()
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

    return depth


#── Helper: Create tree from list ─────────────────────────────────────────────────────

def build(values: list[int | None]) -> TreeNode | None:
    if not values or values[0] is None:
        return None
    root = TreeNode(values[0])
    q: deque[TreeNode] = deque([root])
    i = 1
    while q and i < len(values):
        node = q.popleft()
        if i < len(values) and values[i] is not None:
            node.left = TreeNode(values[i])
            q.append(node.left)
        i += 1
        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i])
            q.append(node.right)
        i += 1
    return root


#── Example Execution ──────────────────────────────────────────────────────────────
if __name__ == "__main__":
    #        1
    #       / \
    #      2   3
    #     / \   \
    #    4   5   6
    root = build([1, 2, 3, 4, 5, None, 6])

    print("=== Level Order Traversal ===")
    print(f"Basic BFS:         {level_order(root)}")
    print(f"Grouped by Levels: {level_order_by_levels(root)}")
    print(f"Zigzag Traversal: {zigzag_level_order(root)}")
    print(f"Right Side View:  {right_side_view(root)}")
    print(f"Maximum Depth (BFS):  {max_depth_bfs(root)}")

    print()
    print("=== Complete Binary Tree ===")
    #       1
    #      / \
    #     2   3
    #    / \ / \
    #   4  5 6  7
    full = build([1, 2, 3, 4, 5, 6, 7])
    levels = level_order_by_levels(full)
    for i, lv in enumerate(levels):
        print(f"Level {i}: {lv}")

    print()
    print("=== Zigzag Visualization ===")
    #1          Level 0: → [1]
    #         /   \
    #2     3       Level 1: ← [3, 2]
    #       / \   / \
    #4   5 6   7     Level 2: → [4, 5, 6, 7]
    zz = zigzag_level_order(full)
    for i, lv in enumerate(zz):
        direction = "→" if i % 2 == 0 else "←"
        print(f"Level {i} ({direction}): {lv}")