Các thuật toán phổ biến:

1. Tìm độ sâu tối đa của cây nhị phân.
2. Tìm độ sâu tối thiểu của cây nhị phân.
3. Duyệt theo mức của cây nhị phân.
4. Duyệt trước của cây nhị phân.
5. Duyệt giữa của cây nhị phân.
6. Duyệt sau của cây nhị phân.
7. Đếm số lượng nút trong cây nhị phân.
8. Đếm số lượng nút lá trong cây nhị phân.
9. Kiểm tra cây nhị phân có phải là cây cân bằng hay không.
10. Kiểm tra cây nhị phân có phải là cây đầy đủ hay không.
11. Kiểm tra hai cây nhị phân có giống nhau hoàn toàn hay không.
12. Kiểm tra cây nhị phân có phải là cây tìm kiếm nhị phân hợp lệ hay không.
13. Chuyển đổi mảng đã sắp xếp thành cây tìm kiếm nhị phân.
14. Lật ngược cây nhị phân.
15. Duyệt cây nhị phân theo hình chữ Z.
16. Kiểm tra hai cây nhị phân có phải là ảnh soi của nhau hay không.
17. Kiểm tra một cây nhị phân có phải là cây đối xứng hay không.
18. Tìm tổ tiên chung gần nhất của hai nút trong cây nhị phân.
19. Kiểm tra hai nút trong cây nhị phân có phải là anh em họ hay không.

0. Định nghĩa cấu trúc cây nhị phân

struct Node {
    int value;
    Node* leftChild;
    Node* rightChild;
    Node(int val) : value(val), leftChild(nullptr), rightChild(nullptr) {}
};

1. Tìm độ sâu tối đa của cây nhị phân

int findMaxDepth(Node* root) {
    if (root == nullptr) return 0;
    int depthLeft = findMaxDepth(root->leftChild);
    int depthRight = findMaxDepth(root->rightChild);
    return std::max(depthLeft, depthRight) + 1;
}

2. Tìm độ sâu tối thiểu của cây nhị phân

int findMinDepth(Node* root) {
    if (root == nullptr) return 0;
    if (!root->leftChild && !root->rightChild) return 1;
    int minLeft = INT32_MAX, minRight = INT32_MAX;
    if (root->leftChild) minLeft = findMinDepth(root->leftChild);
    if (root->rightChild) minRight = findMinDepth(root->rightChild);
    return std::min(minLeft, minRight) + 1;
}

3. Duyệt theo mức của cây nhị phân

void traverseByLevel(Node* root) {
    if (!root) return;
    std::queue<Node*> queueNodes;
    queueNodes.push(root);
    while (!queueNodes.empty()) {
        int levelSize = queueNodes.size();
        for (int i = 0; i < levelSize; ++i) {
            Node* current = queueNodes.front();
            queueNodes.pop();
            std::cout << current->value << " ";
            if (current->leftChild) queueNodes.push(current->leftChild);
            if (current->rightChild) queueNodes.push(current->rightChild);
        }
        std::cout << std::endl;
    }
}

4. Duyệt trước của cây nhị phân

void preOrderTraversal(Node* root) {
    if (root != nullptr) {
        std::cout << root->value << " ";
        preOrderTraversal(root->leftChild);
        preOrderTraversal(root->rightChild);
    }
}

5. Duyệt giữa của cây nhị phân

void inOrderTraversal(Node* root) {
    if (root != nullptr) {
        inOrderTraversal(root->leftChild);
        std::cout << root->value << " ";
        inOrderTraversal(root->rightChild);
    }
}

6. Duyệt sau của cây nhị phân

void postOrderTraversal(Node* root) {
    if (root != nullptr) {
        postOrderTraversal(root->leftChild);
        postOrderTraversal(root->rightChild);
        std::cout << root->value << " ";
    }
}

7. Đếm số lượng nút trong cây nhị phân

int countNodes(Node* root) {
    if (root == nullptr) return 0;
    return countNodes(root->leftChild) + countNodes(root->rightChild) + 1;
}

8. Đếm số lượng nút lá trong cây nhị phân

int countLeafNodes(Node* root) {
    if (root == nullptr) return 0;
    if (!root->leftChild && !root->rightChild) return 1;
    return countLeafNodes(root->leftChild) + countLeafNodes(root->rightChild);
}

9. Kiểm tra cây nhị phân có phải là cây cân bằng hay không

bool isBalancedTree(Node* root) {
    if (root == nullptr) return true;
    int leftHeight = getHeight(root->leftChild);
    int rightHeight = getHeight(root->rightChild);
    if (std::abs(leftHeight - rightHeight) > 1) return false;
    return isBalancedTree(root->leftChild) && isBalancedTree(root->rightChild);
}

int getHeight(Node* node) {
    if (node == nullptr) return 0;
    return std::max(getHeight(node->leftChild), getHeight(node->rightChild)) + 1;
}

10. Kiểm tra cây nhị phân có phải là cây đầy đủ hay không

bool isFullBinaryTree(Node* root) {
    if (root == nullptr) return true;
    if (root->leftChild == nullptr && root->rightChild == nullptr) return true;
    if (root->leftChild && root->rightChild)
        return isFullBinaryTree(root->leftChild) && isFullBinaryTree(root->rightChild);
    return false;
}

11. Kiểm tra hai cây nhị phân có giống nhau hoàn toàn hay không

bool areTreesIdentical(Node* p, Node* q) {
    if (p == nullptr && q == nullptr) return true;
    if (p == nullptr || q == nullptr) return false;
    return (p->value == q->value &&
            areTreesIdentical(p->leftChild, q->leftChild) &&
            areTreesIdentical(p->rightChild, q->rightChild));
}

12. Kiểm tra cây nhị phân có phải là cây tìm kiếm nhị phân hợp lệ hay không

bool isValidBST(Node* root) {
    return checkBST(root, INT_MIN, INT_MAX);
}

bool checkBST(Node* node, int minVal, int maxVal) {
    if (node == nullptr) return true;
    if (node->value <= minVal || node->value >= maxVal) return false;
    return checkBST(node->leftChild, minVal, node->value) &&
           checkBST(node->rightChild, node->value, maxVal);
}

13. Chuyển đổi mảng đã sắp xếp thành cây tìm kiếm nhị phân

Node* sortedArrayToBST(const std::vector<int>& nums, int start, int end) {
    if (start > end) return nullptr;
    int mid = start + (end - start) / 2;
    Node* root = new Node(nums[mid]);
    root->leftChild = sortedArrayToBST(nums, start, mid - 1);
    root->rightChild = sortedArrayToBST(nums, mid + 1, end);
    return root;
}

Node* convertToBST(const std::vector<int>& nums) {
    return sortedArrayToBST(nums, 0, nums.size() - 1);
}

14. Lật ngược cây nhị phân

Node* invertBinaryTree(Node* root) {
    if (root == nullptr) return nullptr;
    std::swap(root->leftChild, root->rightChild);
    invertBinaryTree(root->leftChild);
    invertBinaryTree(root->rightChild);
    return root;
}

15. Duyệt cây nhị phân theo hình chữ Z

std::vector<std::vector<int>> zigzagTraversal(Node* root) {
    std::vector<std::vector<int>> result;
    if (root == nullptr) return result;
    std::deque<Node*> queue;
    queue.push_back(root);
    bool reverseOrder = false;
    while (!queue.empty()) {
        int levelSize = queue.size();
        std::vector<int> currentLevel;
        for (int i = 0; i < levelSize; ++i) {
            Node* node = queue.front();
            queue.pop_front();
            currentLevel.push_back(node->value);
            if (node->leftChild) queue.push_back(node->leftChild);
            if (node->rightChild) queue.push_back(node->rightChild);
        }
        if (reverseOrder) std::reverse(currentLevel.begin(), currentLevel.end());
        reverseOrder = !reverseOrder;
        result.push_back(currentLevel);
    }
    return result;
}

16. Kiểm tra hai cây nhị phân có phải là ảnh soi của nhau hay không

bool areMirrorImages(Node* p, Node* q) {
    if (p == nullptr && q == nullptr) return true;
    if (p == nullptr || q == nullptr) return false;
    return (p->value == q->value &&
            areMirrorImages(p->leftChild, q->rightChild) &&
            areMirrorImages(p->rightChild, q->leftChild));
}

17. Kiểm tra một cây nhị phân có phải là cây đối xứng hay không

bool isSymmetricTree(Node* root) {
    if (root == nullptr) return true;
    return areMirrorImages(root->leftChild, root->rightChild);
}

18. Tìm tổ tiên chung gần nhất của hai nút trong cây nhị phân

Node* findLowestCommonAncestor(Node* root, Node* p, Node* q) {
    if (root == nullptr || root == p || root == q) return root;
    Node* left = findLowestCommonAncestor(root->leftChild, p, q);
    Node* right = findLowestCommonAncestor(root->rightChild, p, q);
    if (left && right) return root;
    return left ? left : right;
}

19. Kiểm tra hai nút trong cây nhị phân có phải là anh em họ hay không

bool areCousins(Node* root, Node* p, Node* q) {
    if (root == nullptr || p == nullptr || q == nullptr) return false;
    std::queue<std::pair<Node*, int>> queueNodes;
    queueNodes.push({root, 0});
    std::pair<Node*, int> pNode, qNode;
    while (!queueNodes.empty()) {
        auto current = queueNodes.front();
        queueNodes.pop();
        if (current.first == p) pNode = current;
        if (current.first == q) qNode = current;
        if (current.first->leftChild)
            queueNodes.push({current.first->leftChild, current.second + 1});
        if (current.first->rightChild)
            queueNodes.push({current.first->rightChild, current.second + 1});
    }
    return (pNode.second == qNode.second &&
            pNode.first->value != qNode.first->value);
}