Question

How to parse a table into a binary tree in TypeScript

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 {
    id: number;
    name: string;
    left: Node | null;   // first child
    right: Node | null;  // next sibling

    constructor(id: number, name: string) {
        this.id = id;
        this.name = name;
        this.left = null;
        this.right = null;
    }
}

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

function printTree(root: Node | null, depth: number = 0): void {
    if (root === null) return;

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

    // Indent the node itself
    const indent: string = "  ".repeat(depth + 1);
    const idFormatted: string = root.id.toString().padStart(2, "0");
    console.log(`${indent}${idFormatted} - ${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
   ------------------------------------------------------------ */

interface Row {
    id: number;
    name: string;
    parentId: number;
}

function buildTree(table: Row[]): Node | null {
    // Create nodes
    const nodesOut: Map<number, Node> = new Map<number, Node>();
    for (const row of table) {
        const id: number = row.id;
        const name: string = row.name;
        nodesOut.set(id, new Node(id, name));
    }

    let root: Node | null = null;

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

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

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

    return root;
}

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

const table: Row[] = [
    { 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 }
];

const root: Node | null = buildTree(table);

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