Idea:

Traversal = duyệt qua tất cả các node trong cây.

Có 2 hướng tiếp cận chính:

🌿 Common Tree structure

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

Ví dụ cây mẫu:

       1
      / \\
     2   3
    / \\
   4   5

🕳️ DFS (Depth First Search)

DFS có 3 kiểu phổ biến:

Loại Thứ tự duyệt Code
Inorder Left → Root → Right Dùng cho BST để ra dãy sorted
Preorder Root → Left → Right Dùng để copy / serialize cây
Postorder Left → Right → Root Dùng để delete hoặc tính tổng cây

🔹 Inorder Traversal

def inorder(root):
    if not root:
        return
    inorder(root.left)
    print(root.val)
    inorder(root.right)

Output cho cây ví dụ:

→ 4 2 5 1 3