Dưới đây là triển khai đầy đủ ba kiểu duyệt cây nhị phân — tiền thứ tự (preorder), trung thứ tự (inorder), hậu thứ tự (postorder) — bằng cả hai phương pháp: đệ quy và không đệ quy (dùng ngăn xếp). Mỗi hàm ghi nhận giá trị nút theo thứ tự tương ứng vào một vector đã cho.

Phiên bản đệ quy

struct TreeNode {
    int data;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : data(x), left(nullptr), right(nullptr) {}
};

class BinaryTreeTraversal {
public:
    void preorderRecursive(TreeNode* node, std::vector<int>& result) {
        if (!node) return;
        result.push_back(node->data);
        preorderRecursive(node->left, result);
        preorderRecursive(node->right, result);
    }

    void inorderRecursive(TreeNode* node, std::vector<int>& result) {
        if (!node) return;
        inorderRecursive(node->left, result);
        result.push_back(node->data);
        inorderRecursive(node->right, result);
    }

    void postorderRecursive(TreeNode* node, std::vector<int>& result) {
        if (!node) return;
        postorderRecursive(node->left, result);
        postorderRecursive(node->right, result);
        result.push_back(node->data);
    }

    std::vector<std::vector<int>> getAllSequencesRecursive(TreeNode* root) {
        std::vector<std::vector<int>> output;
        std::vector<int> pre, in, post;

        preorderRecursive(root, pre);
        inorderRecursive(root, in);
        postorderRecursive(root, post);

        output.push_back(pre);
        output.push_back(in);
        output.push_back(post);
        return output;
    }
};

Phiên bản lặp (không đệ quy)

Đối với duyệt hậu thứ tự, thay vì dùng hai ngăn xếp hoặc đánh dấu nút đã thăm, ta tận dụng tính chất: hậu thứ tự (left → right → root) là đảo ngược của duyệt phải-trái-gốc (root → right → left). Do đó, ta thực hiện duyệt "phải-trái-gốc" (giống tiền thứ tự nhưng ưu tiên nhánh phải), rồi lật mảng kết quả.

class BinaryTreeTraversal {
public:
    void preorderIterative(TreeNode* root, std::vector<int>& result) {
        if (!root) return;
        std::stack<TreeNode*> stack;
        stack.push(root);

        while (!stack.empty()) {
            TreeNode* current = stack.top();
            stack.pop();
            result.push_back(current->data);
            if (current->right) stack.push(current->right);
            if (current->left)  stack.push(current->left);
        }
    }

    void inorderIterative(TreeNode* root, std::vector<int>& result) {
        std::stack<TreeNode*> stack;
        TreeNode* curr = root;

        while (curr || !stack.empty()) {
            while (curr) {
                stack.push(curr);
                curr = curr->left;
            }
            curr = stack.top();
            stack.pop();
            result.push_back(curr->data);
            curr = curr->right;
        }
    }

    void postorderIterative(TreeNode* root, std::vector<int>& result) {
        if (!root) return;
        std::stack<TreeNode*> stack;
        TreeNode* curr = root;

        while (curr || !stack.empty()) {
            while (curr) {
                result.push_back(curr->data);
                stack.push(curr);
                curr = curr->right; // ưu tiên nhánh phải
            }
            curr = stack.top();
            stack.pop();
            curr = curr->left;
        }
        std::reverse(result.begin(), result.end());
    }

    std::vector<std::vector<int>> getAllSequencesIterative(TreeNode* root) {
        std::vector<std::vector<int>> output;
        std::vector<int> pre, in, post;

        preorderIterative(root, pre);
        inorderIterative(root, in);
        postorderIterative(root, post);

        output.push_back(pre);
        output.push_back(in);
        output.push_back(post);
        return output;
    }
};