binary_tree.hpp

Go to the documentation of this file.

#ifndef BINARY_TREE_H
#define BINARY_TREE_H
 
#include <functional>
#include <vector>
#include <optional>
#include <queue>
#include <cassert>
#include <unordered_map>
 
namespace hsc_snippets {
    struct TreeNode {
        int val;
        TreeNode *left;
        TreeNode *right;
 
        TreeNode() : val(0), left(nullptr), right(nullptr) {}
 
        TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 
        TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
    };
 
    static TreeNode *new_binary_tree(const std::vector<std::optional<int>> v) {
        if (v.empty()) {
            return nullptr;
        }
 
        const auto n = v.size();
 
        assert(v[0].has_value());
 
        auto root = new TreeNode(v[0].value());
        auto q = std::queue<TreeNode *>{};
        q.push(root);
        int i = 1;
 
        while (i < n) {
            auto node = q.front();
            q.pop();
            if (v[i].has_value()) {
                node->left = new TreeNode(v[i].value());
                q.push(node->left);
            }
            i += 1;
            if (i >= n) {
                break;
            }
            if (v[i].has_value()) {
                node->right = new TreeNode(v[i].value());
                q.push(node->right);
            }
            i += 1;
        }
 
        return root;
    }
 
    static std::vector<std::optional<int>> binary_tree_to_vector(TreeNode *root) {
        if (!root) {
            return {};
        }
 
        std::vector<std::optional<int>> result;
        std::queue<TreeNode *> q;
        q.push(root);
 
        while (!q.empty()) {
            TreeNode *node = q.front();
            q.pop();
 
            if (node) {
                result.emplace_back(node->val);
                q.push(node->left);
                q.push(node->right);
            } else {
                result.emplace_back(std::nullopt);
            }
        }
 
        // Remove trailing nullopts for a more compact representation
        while (!result.empty() && !result.back().has_value()) {
            result.pop_back();
        }
 
        return result;
    }
 
    static void delete_binary_tree(TreeNode *root) {
        if (root == nullptr)
            return;
        delete_binary_tree(root->left);
        delete_binary_tree(root->right);
        delete root;
    }
 
    static int get_binary_tree_depth(TreeNode *root) {
        if (root == nullptr)
            return 0;
        int depth = 1;
        depth = std::max(depth, get_binary_tree_depth(root->left) + 1);
        depth = std::max(depth, get_binary_tree_depth(root->right) + 1);
        return depth;
    }
 
    static void inorder(TreeNode *root, std::function<void(int)> func) {
        if (root == nullptr)
            return;
        inorder(root->left, func);
        func(root->val);
        inorder(root->right, func);
    }
 
    static void preorder(TreeNode *root, std::function<void(int)> func) {
        if (root == nullptr)
            return;
        func(root->val);
        preorder(root->left, func);
        preorder(root->right, func);
    }
 
    static void postorder(TreeNode *root, std::function<void(int)> func) {
        if (root == nullptr)
            return;
 
        postorder(root->left, func);
        postorder(root->right, func);
        func(root->val);
    }
 
    static std::unordered_map<int, std::vector<int>> binary_tree_to_adjacency_list(TreeNode *root) {
        auto adjacencyList = std::unordered_map<int, std::vector<int>>{};
        if (root == nullptr) {
            return adjacencyList;
        }
        auto q = std::queue<TreeNode *>{};
        q.push(root);
        while (!q.empty()) {
            auto node = q.front();
            q.pop();
            if (node->left != nullptr) {
                adjacencyList[node->left->val].push_back(node->val);
                adjacencyList[node->val].push_back(node->left->val);
                q.push(node->left);
            }
            if (node->right != nullptr) {
                adjacencyList[node->right->val].push_back(node->val);
                adjacencyList[node->val].push_back(node->right->val);
                q.push(node->right);
            }
        }
 
        return adjacencyList;
    }
 
}
 
#endif // BINARY_TREE_H