1
        /   \
       2     3
      / \     \
     4   5     6
    /
   7

Travessias:
  In-order (E-R-D):   7, 4, 2, 5, 1, 3, 6
  Pre-order (R-E-D):  1, 2, 4, 7, 5, 3, 6
  Post-order (E-D-R): 7, 4, 5, 2, 6, 3, 1
  Level-order (BFS):  1, 2, 3, 4, 5, 6, 7

Propriedades:
  Altura: 3  (caminho mais longo da raiz até folha)
  Nós: 7
  Folhas: 3  (nós 7, 5, 6)

const std = @import("std");
const Allocator = std.mem.Allocator;

/// Árvore binária genérica.
pub fn ArvoreBinaria(comptime T: type) type {
    return struct {
        const Self = @This();

        pub const No = struct {
            valor: T,
            esquerdo: ?*No,
            direito: ?*No,
        };

        raiz: ?*No,
        allocator: Allocator,

        pub fn init(allocator: Allocator) Self {
            return .{ .raiz = null, .allocator = allocator };
        }

        pub fn deinit(self: *Self) void {
            liberarSubarvore(self.allocator, self.raiz);
            self.raiz = null;
        }

        fn liberarSubarvore(allocator: Allocator, no: ?*No) void {
            if (no) |n| {
                liberarSubarvore(allocator, n.esquerdo);
                liberarSubarvore(allocator, n.direito);
                allocator.destroy(n);
            }
        }

        /// Cria um novo nó.
        pub fn criarNo(self: *Self, valor: T) !*No {
            const no = try self.allocator.create(No);
            no.* = .{ .valor = valor, .esquerdo = null, .direito = null };
            return no;
        }

        /// Altura da árvore.
        pub fn altura(self: *const Self) usize {
            return alturaNo(self.raiz);
        }

        fn alturaNo(no: ?*const No) usize {
            if (no == null) return 0;
            const n = no.?;
            const h_esq = alturaNo(n.esquerdo);
            const h_dir = alturaNo(n.direito);
            return 1 + @max(h_esq, h_dir);
        }

        /// Número total de nós.
        pub fn contarNos(self: *const Self) usize {
            return contarSubarvore(self.raiz);
        }

        fn contarSubarvore(no: ?*const No) usize {
            if (no == null) return 0;
            const n = no.?;
            return 1 + contarSubarvore(n.esquerdo) + contarSubarvore(n.direito);
        }

        /// Travessia in-order (esquerdo, raiz, direito).
        pub fn inOrder(self: *const Self, allocator: Allocator) ![]T {
            var resultado = std.ArrayList(T).init(allocator);
            inOrderHelper(self.raiz, &resultado) catch {};
            return try resultado.toOwnedSlice();
        }

        fn inOrderHelper(no: ?*const No, resultado: *std.ArrayList(T)) !void {
            if (no == null) return;
            const n = no.?;
            try inOrderHelper(n.esquerdo, resultado);
            try resultado.append(n.valor);
            try inOrderHelper(n.direito, resultado);
        }

        /// Travessia pre-order (raiz, esquerdo, direito).
        pub fn preOrder(self: *const Self, allocator: Allocator) ![]T {
            var resultado = std.ArrayList(T).init(allocator);
            preOrderHelper(self.raiz, &resultado) catch {};
            return try resultado.toOwnedSlice();
        }

        fn preOrderHelper(no: ?*const No, resultado: *std.ArrayList(T)) !void {
            if (no == null) return;
            const n = no.?;
            try resultado.append(n.valor);
            try preOrderHelper(n.esquerdo, resultado);
            try preOrderHelper(n.direito, resultado);
        }

        /// Travessia post-order (esquerdo, direito, raiz).
        pub fn postOrder(self: *const Self, allocator: Allocator) ![]T {
            var resultado = std.ArrayList(T).init(allocator);
            postOrderHelper(self.raiz, &resultado) catch {};
            return try resultado.toOwnedSlice();
        }

        fn postOrderHelper(no: ?*const No, resultado: *std.ArrayList(T)) !void {
            if (no == null) return;
            const n = no.?;
            try postOrderHelper(n.esquerdo, resultado);
            try postOrderHelper(n.direito, resultado);
            try resultado.append(n.valor);
        }

        /// Travessia level-order (BFS).
        pub fn levelOrder(self: *const Self, allocator: Allocator) ![]T {
            var resultado = std.ArrayList(T).init(allocator);
            if (self.raiz == null) return try resultado.toOwnedSlice();

            var fila = std.ArrayList(*const No).init(allocator);
            defer fila.deinit();
            try fila.append(self.raiz.?);

            while (fila.items.len > 0) {
                const no = fila.orderedRemove(0);
                try resultado.append(no.valor);
                if (no.esquerdo) |e| try fila.append(e);
                if (no.direito) |d| try fila.append(d);
            }

            return try resultado.toOwnedSlice();
        }

        /// Verifica se é espelho (simétrica).
        pub fn ehSimetrica(self: *const Self) bool {
            if (self.raiz == null) return true;
            return espelho(self.raiz.?.esquerdo, self.raiz.?.direito);
        }

        fn espelho(a: ?*const No, b: ?*const No) bool {
            if (a == null and b == null) return true;
            if (a == null or b == null) return false;
            return a.?.valor == b.?.valor and
                espelho(a.?.esquerdo, b.?.direito) and
                espelho(a.?.direito, b.?.esquerdo);
        }
    };
}

pub fn main() !void {
    const stdout = std.io.getStdOut().writer();
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();

    var arvore = ArvoreBinaria(i32).init(allocator);
    defer arvore.deinit();

    // Constrói árvore manualmente
    arvore.raiz = try arvore.criarNo(1);
    arvore.raiz.?.esquerdo = try arvore.criarNo(2);
    arvore.raiz.?.direito = try arvore.criarNo(3);
    arvore.raiz.?.esquerdo.?.esquerdo = try arvore.criarNo(4);
    arvore.raiz.?.esquerdo.?.direito = try arvore.criarNo(5);
    arvore.raiz.?.direito.?.direito = try arvore.criarNo(6);
    arvore.raiz.?.esquerdo.?.esquerdo.?.esquerdo = try arvore.criarNo(7);

    try stdout.print("Altura: {d}\n", .{arvore.altura()});
    try stdout.print("Nós: {d}\n", .{arvore.contarNos()});

    // Travessias
    const inorder = try arvore.inOrder(allocator);
    defer allocator.free(inorder);
    try stdout.print("In-order:    ", .{});
    for (inorder) |v| try stdout.print("{d} ", .{v});
    try stdout.print("\n", .{});

    const preorder = try arvore.preOrder(allocator);
    defer allocator.free(preorder);
    try stdout.print("Pre-order:   ", .{});
    for (preorder) |v| try stdout.print("{d} ", .{v});
    try stdout.print("\n", .{});

    const postorder = try arvore.postOrder(allocator);
    defer allocator.free(postorder);
    try stdout.print("Post-order:  ", .{});
    for (postorder) |v| try stdout.print("{d} ", .{v});
    try stdout.print("\n", .{});

    const levelorder = try arvore.levelOrder(allocator);
    defer allocator.free(levelorder);
    try stdout.print("Level-order: ", .{});
    for (levelorder) |v| try stdout.print("{d} ", .{v});
    try stdout.print("\n", .{});
}