Question

How to parse a table into a binary tree in JavaScript

Answer 1

/**
 * Parse a table of (id, name, parentId) into a binary tree using
 * the Left‑Child / Right‑Sibling representation.
 *
 * Why this representation?
 * - The table describes a general tree (each node can have many children).
 * - A binary tree requires each node to have at most two pointers.
 * - left  -> first child
 * - right -> next sibling
 *
 * This preserves the full structure while staying inside a binary tree model.
 */

class Node {
    constructor(id, name) {
        this.id = id;
        this.name = name;
        this.left = null;   // first child
        this.right = null;  // next sibling
    }
}

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

function printTree(root, depth = 0) {
    if (!root) return;

    // Print ROOT on its own line
    if (depth === 0) {
        console.log("ROOT");
    }

    // Indent the node itself
    console.log("  ".repeat(depth + 1) + `${root.id.toString().padStart(2, "0")} - ${root.name}`);

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

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

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

function buildTree(table) {
    const nodesOut = new Map();

    // Create nodes
    for (const row of table) {
        nodesOut.set(row.id, new Node(row.id, row.name));
    }

    let root = null;

    // Attach children and siblings
    for (const row of table) {
        const current = nodesOut.get(row.id);

        if (row.parentId === 0) {
            // top-level node → sibling chain under root
            if (!root) {
                root = current;
            } else {
                let p = root;
                while (p.right) p = p.right;
                p.right = current;
            }
        } else {
            const parent = nodesOut.get(row.parentId);

            // attach as first child or next sibling
            if (!parent.left) {
                parent.left = current;
            } else {
                let p = parent.left;
                while (p.right) p = p.right;
                p.right = current;
            }
        }
    }

    return root;
}

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

// Example table
const table = [
    { id: 1,  name: "Node 1",        parentId: 0 },
    { id: 2,  name: "Node 1.1",      parentId: 1 },
    { id: 3,  name: "Node 2",        parentId: 0 },
    { id: 4,  name: "Node 1.1.1",    parentId: 2 },
    { id: 5,  name: "Node 2.1",      parentId: 3 },
    { id: 6,  name: "Node 2.3.1",    parentId: 3 },
    { id: 7,  name: "Node 1.2",      parentId: 1 },
    { id: 8,  name: "Node 1.3",      parentId: 1 },
    { id: 9,  name: "Node 1.3.1",    parentId: 8 },
    { id: 10, name: "Node 2.4",      parentId: 3 },
    { id: 11, name: "Node 2.1.1",    parentId: 5 },
    { id: 12, name: "Node 2.1.1.6",  parentId: 11 }
];

// Build tree
const root = buildTree(table);

// Print
printTree(root);



/*
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