Implement tree and forest in zig

traversal_binary_tree.zig

const std = @import("std");

var gpa = std.heap.GeneralPurposeAllocator(.{}){};

const allocator = gpa.allocator();

// We need to construct a struct type for binary tree
const TreeNode = struct {
    data: u8,
    l_child: ?*TreeNode,
    r_child: ?*TreeNode,
};

// this is main run logic
pub fn main() !void {
    // we need to remember to deinit the gpa!
    defer {
        const leaked = gpa.deinit();
        if (leaked) std.testing.expect(false) catch @panic("TEST FAIL"); //fail test; can't try in defer as defer is executed after we return
    }

    var node_2 = try new_node(2, null, null);
    // remember destroy the node
    defer allocator.destroy(node_2);

    var node_3 = try new_node(3, null, null);
    // remember destroy the node
    defer allocator.destroy(node_3);

    var node_root = try new_node(1, node_2, node_3);
    // remember destroy the node
    defer allocator.destroy(node_root);

    var list = std.ArrayList(*TreeNode).init(allocator);
    // remember deinit the list
    defer list.deinit();

    try list.append(node_root);

    // Here, we clone the arraylist
    var list_1 = try list.clone();
    // remember deinit the list
    defer list_1.deinit();

    // Here, we clone the arraylist
    var list_2 = try list.clone();
    // remember deinit the list
    defer list_2.deinit();

    try pre_order_traversal(&list);
    try in_order_traversal(&list_1);
    try post_order_traversal(&list_2);
}

fn new_node(data: u8, l_Child: ?*TreeNode, r_child: ?*TreeNode) !*TreeNode {
    var node = try allocator.create(TreeNode);
    node.data = data;
    node.l_child = l_Child;
    node.r_child = r_child;
    return node;
}

fn do_something(data: u8) void {
    std.log.info("element is {}\n", .{data});
}

// pre order traversal
fn pre_order_traversal(list: *std.ArrayList(*TreeNode)) !void {
    var last = list.*.popOrNull();
    if (last != null) {
        do_something(last.?.data);
        if (last.?.l_child != null) {
            try list.*.append(last.?.l_child.?);
            try pre_order_traversal(list);
        }
        if (last.?.r_child != null) {
            try list.*.append(last.?.r_child.?);
            try pre_order_traversal(list);
        }
    }
}

// in order traversal
fn in_order_traversal(list: *std.ArrayList(*TreeNode)) !void {
    var last = list.*.popOrNull();
    if (last != null) {
        if (last.?.l_child != null) {
            try list.*.append(last.?.l_child.?);
            try pre_order_traversal(list);
        }
        do_something(last.?.data);
        if (last.?.r_child != null) {
            try list.*.append(last.?.r_child.?);
            try pre_order_traversal(list);
        }
    }
}

// post order traversal
fn post_order_traversal(list: *std.ArrayList(*TreeNode)) !void {
    var last = list.*.popOrNull();
    if (last != null) {
        if (last.?.l_child != null) {
            try list.*.append(last.?.l_child.?);
            try pre_order_traversal(list);
        }
        if (last.?.r_child != null) {
            try list.*.append(last.?.r_child.?);
            try pre_order_traversal(list);
        }
        do_something(last.?.data);
    }
}