Question

How to parse a table into a binary tree in C++

Answer 1

#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>

struct Node {
    int id;
    std::string name;

    Node* left;   // first child
    Node* right;  // next sibling

    Node(int i, const std::string& n)
        : id(i), name(n), left(nullptr), right(nullptr) {}
};

/* -------------------- Print Tree -------------------- */

void printTree(Node* root, int depth = 0) {
    if (!root) return;

    // Print ROOT on its own line
    if (depth == 0) {
        std::cout << "ROOT\n";
    }

    // Indent the node itself
    for (int i = 0; i < depth + 1; ++i)
        std::cout << "  ";

    // print ID with leading zero if needed
    std::cout << (root->id < 10 ? "0" : "") << root->id
              << " - " << root->name << "\n";

    // first child
    printTree(root->left, depth + 1);

    // next sibling (another top-level node)
    if (depth == 0 && root->right != nullptr) {
        printTree(root->right, 0);   // restart ROOT
    } else {
        printTree(root->right, depth);
    }
}

/* ------------------------------------------------------------
   Build the tree using Left-Child / Right-Sibling representation
   ------------------------------------------------------------ */

Node* buildTree(
    const std::vector<std::tuple<int, std::string, int>>& table,
    std::unordered_map<int, Node*>& nodesOut
) {
    // Create nodes
    for (const auto& row : table) {
        int id = std::get<0>(row);
        const std::string& name = std::get<1>(row);
        nodesOut[id] = new Node(id, name);
    }

    Node* root = nullptr;

    // Attach children and siblings
    for (const auto& row : table) {
        int id = std::get<0>(row);
        int parentId = std::get<2>(row);

        Node* current = nodesOut[id];

        if (parentId == 0) {
            // top-level node → sibling chain under root
            if (!root) {
                root = current;
            } else {
                Node* p = root;
                while (p->right) p = p->right;
                p->right = current;
            }
        } else {
            Node* parent = nodesOut[parentId];

            // attach as first child or next sibling
            if (!parent->left) {
                parent->left = current;
            } else {
                Node* p = parent->left;
                while (p->right) p = p->right;
                p->right = current;
            }
        }
    }

    return root;
}

/* -------------------- Main -------------------- */

int main() {
    // Example table
    std::vector<std::tuple<int, std::string, int>> table = {
      // Id  Name             ParentId 
        { 1, "Node 1",        0},
        { 2, "Node 1.1",      1},
        { 3, "Node 2",        0},
        { 4, "Node 1.1.1",    2},
        { 5, "Node 2.1",      3},
        { 6, "Node 2.3.1",    3},
        { 7, "Node 1.2",      1},
        { 8, "Node 1.3",      1},
        { 9, "Node 1.3.1",    8},
        {10, "Node 2.4",      3},
        {11, "Node 2.1.1",    5},
        {12, "Node 2.1.1.6", 11},
    };

    std::unordered_map<int, Node*> nodes;

    // Build tree
    Node* root = buildTree(table, nodes);

    // Print
    printTree(root);

    // Cleanup
    for (auto& kv : nodes) delete kv.second;
}


/*
run:

ROOT
  01 - Node 1
    02 - Node 1.1
      04 - Node 1.1.1
    07 - Node 1.2
    08 - Node 1.3
      09 - Node 1.3.1
ROOT
  03 - Node 2
    05 - Node 2.1
      11 - Node 2.1.1
        12 - Node 2.1.1.6
    06 - Node 2.3.1
    10 - Node 2.4

*/

 

70+ SQL courses for beginners and professionals