Question

How to parse a table into a binary tree in Java

Answer 1

import java.util.Map;
import java.util.List;
import java.util.Arrays;
import java.util.HashMap;

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

/** A single unified data structure for each row */
class Row {
    int id;
    String name;
    int parentId;

    Row(int id, String name, int parentId) {
        this.id = id;
        this.name = name;
        this.parentId = parentId;
    }
}

class Node {
    int id;
    String name;

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

    Node(int id, String name) {
        this.id = id;
        this.name = name;
    }
}

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

class TreePrinter {

    // Print the tree with indentation and explicit ROOT marker
    static void print(Node root, int depth) {
        if (root == null) return;

        // Print ROOT on its own line
        if (depth == 0) {
            System.out.println("ROOT");
        }

        // indentation for the node itself
        for (int i = 0; i < depth + 1; i++) {
            System.out.print("  ");
        }

        // print ID with leading zero if needed
        System.out.printf("%02d - %s%n", root.id, root.name);

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

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

/** -------------------- Build Tree -------------------- */

class TreeBuilder {

    static Node buildTree(
            List<Row> table,               // unified row structure
            Map<Integer, Node> nodesOut    // id -> Node
    ) {
        // Create nodes
        for (Row row : table) {
            nodesOut.put(row.id, new Node(row.id, row.name));
        }

        Node root = null;

        // Attach children and siblings
        for (Row row : table) {
            Node current = nodesOut.get(row.id);

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

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

        return root;
    }
}

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

public class Main {

    public static void main(String[] args) {

        // Example table (single unified structure)
        List<Row> table = Arrays.asList(
                 // Id   Name            ParentId 
            new Row(1,  "Node 1",        0),
            new Row(2,  "Node 1.1",      1),
            new Row(3,  "Node 2",        0),
            new Row(4,  "Node 1.1.1",    2),
            new Row(5,  "Node 2.1",      3),
            new Row(6,  "Node 2.3.1",    3),
            new Row(7,  "Node 1.2",      1),
            new Row(8,  "Node 1.3",      1),
            new Row(9,  "Node 1.3.1",    8),
            new Row(10, "Node 2.4",      3),
            new Row(11, "Node 2.1.1",    5),
            new Row(12, "Node 2.1.1.6", 11)
        );

        Map<Integer, Node> nodes = new HashMap<>();

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

        // Print
        TreePrinter.print(root, 0);
    }
}


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