DFS แบบลำดับกลาง ก่อน และหลัง

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# Build: 1 -> left=2(left=4,right=5), right=3
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
# pre:  1 2 4 5 3
# in:   4 2 5 1 3
# post: 4 5 2 3 1
print('Tree built successfully')

def preorder(root):
    if not root:
        return []
    return [root.val] + preorder(root.left) + preorder(root.right)

# More memory-efficient with an accumulator:
def preorder_v2(root, result=None):
    if result is None:
        result = []
    if not root:
        return result
    result.append(root.val)  # PROCESS ROOT FIRST
    preorder_v2(root.left, result)
    preorder_v2(root.right, result)
    return result

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(preorder_v2(root))  # [1, 2, 4, 5, 3]

def inorder(root, result=None):
    if result is None:
        result = []
    if not root:
        return result
    inorder(root.left, result)   # left subtree first
    result.append(root.val)      # PROCESS ROOT MIDDLE
    inorder(root.right, result)  # right subtree last
    return result

# For a BST, inorder gives sorted output:
from collections import deque
def make_bst():
    root = TreeNode(4)
    root.left = TreeNode(2)
    root.right = TreeNode(6)
    root.left.left = TreeNode(1)
    root.left.right = TreeNode(3)
    return root

bst = make_bst()
print(inorder(bst))  # [1, 2, 3, 4, 6] - sorted!

def postorder(root, result=None):
    if result is None:
        result = []
    if not root:
        return result
    postorder(root.left, result)   # left subtree
    postorder(root.right, result)  # right subtree
    result.append(root.val)        # PROCESS ROOT LAST
    return result

# Use case: delete a tree (children before parent)
def delete_tree(root):
    if not root:
        return
    delete_tree(root.left)
    delete_tree(root.right)
    print(f'Deleting node {root.val}')  # safe: children gone

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
print(postorder(root))  # [4, 2, 3, 1]

def preorder_iterative(root):
    if not root:
        return []
    result = []
    stack = [root]
    while stack:
        node = stack.pop()
        result.append(node.val)      # process now
        if node.right:               # push right FIRST
            stack.append(node.right)
        if node.left:                # push left second (popped first)
            stack.append(node.left)
    return result

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(preorder_iterative(root))  # [1, 2, 4, 5, 3]

def inorder_iterative(root):
    result = []
    stack = []
    curr = root
    while curr or stack:
        # Go as far left as possible
        while curr:
            stack.append(curr)
            curr = curr.left
        # Pop and process
        curr = stack.pop()
        result.append(curr.val)
        # Move to right subtree
        curr = curr.right
    return result

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(inorder_iterative(root))  # [4, 2, 5, 1, 3]

from collections import deque

def postorder_iterative(root):
    if not root:
        return []
    result = deque()
    stack = [root]
    while stack:
        node = stack.pop()
        result.appendleft(node.val)  # prepend = reverse pre-order
        if node.left:
            stack.append(node.left)  # push left first
        if node.right:
            stack.append(node.right) # push right second
    return list(result)

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(postorder_iterative(root))  # [4, 5, 2, 3, 1]

# Pattern summary:
# Pre-order  -> top-down: parent info flows DOWN to children
# In-order   -> BST sorted property, kth element, validate BST
# Post-order -> bottom-up: children info flows UP to parent
# BFS        -> shortest path, level grouping, level averages

# Example: compute subtree sum (post-order because
# we need left + right sum before computing total)
def subtree_sum(root):
    if not root:
        return 0
    left = subtree_sum(root.left)
    right = subtree_sum(root.right)
    return root.val + left + right  # uses children FIRST

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
print(subtree_sum(root))  # 6

def morris_inorder(root):
    result = []
    curr = root
    while curr:
        if not curr.left:
            result.append(curr.val)
            curr = curr.right
        else:
            # Find in-order predecessor
            pred = curr.left
            while pred.right and pred.right != curr:
                pred = pred.right
            if not pred.right:
                # Make thread and move left
                pred.right = curr
                curr = curr.left
            else:
                # Remove thread, visit, move right
                pred.right = None
                result.append(curr.val)
                curr = curr.right
    return result

root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
print(morris_inorder(root))  # [1, 2, 3, 4, 6]

def build_from_preorder_inorder(preorder, inorder):
    if not preorder:
        return None
    root_val = preorder[0]
    root = TreeNode(root_val)
    mid = inorder.index(root_val)
    # left subtree: inorder[0:mid], preorder[1:mid+1]
    root.left = build_from_preorder_inorder(
        preorder[1:mid+1], inorder[:mid])
    # right subtree: inorder[mid+1:], preorder[mid+1:]
    root.right = build_from_preorder_inorder(
        preorder[mid+1:], inorder[mid+1:])
    return root

pre = [3, 9, 20, 15, 7]
ino = [9, 3, 15, 20, 7]
root = build_from_preorder_inorder(pre, ino)
print(root.val, root.left.val, root.right.val)  # 3 9 20

# Complexity table:
# Traversal  | Time | Space (recursion) | Space (iterative)
# -----------|------|-------------------|------------------
# Pre-order  | O(n) | O(h)              | O(h)
# In-order   | O(n) | O(h)              | O(h)
# Post-order | O(n) | O(h)              | O(h)
# Morris     | O(n) | O(1)              | O(1)
# BFS        | O(n) | O(w)              | O(w)
# h = height, w = max width
# Balanced: h = log n, w = n/2
# Skewed: h = n, w = 1
print('O(n) time for all traversals')