Question

How to parse a table into a binary tree in Go

Answer 1

package main

import (
    "fmt"
    "strings"
)

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

// Node represents a single tree node
type Node struct {
    ID    int
    Name  string
    Left  *Node // first child
    Right *Node // next sibling
}

// Row represents one row of the input table
type Row struct {
    ID       int
    Name     string
    ParentID int
}

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

// printTree prints the tree with indentation and explicit ROOT markers
func printTree(root *Node, depth int) {
    if root == nil {
        return
    }

    // Print ROOT on its own line
    if depth == 0 {
        fmt.Println("ROOT")
    }

    // Indent the node itself
    indent := strings.Repeat("  ", depth+1)

    // Print ID with leading zero if needed
    fmt.Printf("%s%02d - %s\n", indent, root.ID, root.Name)

    // First child
    printTree(root.Left, depth+1)

    // Next sibling (another top-level node)
    if depth == 0 && root.Right != nil {
        printTree(root.Right, 0) // restart ROOT
    } else {
        printTree(root.Right, depth)
    }
}

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

func buildTree(table []Row) *Node {
    // Create nodes
    nodesOut := make(map[int]*Node)
    for _, row := range table {
        nodesOut[row.ID] = &Node{
            ID:   row.ID,
            Name: row.Name,
        }
    }

    var root *Node

    // Attach children and siblings
    for _, row := range table {
        current := nodesOut[row.ID]

        if row.ParentID == 0 {
            // top-level node → sibling chain under root
            if root == nil {
                root = current
            } else {
                p := root
                for p.Right != nil {
                    p = p.Right
                }
                p.Right = current
            }
        } else {
            parent := nodesOut[row.ParentID]

            // attach as first child or next sibling
            if parent.Left == nil {
                parent.Left = current
            } else {
                p := parent.Left
                for p.Right != nil {
                    p = p.Right
                }
                p.Right = current
            }
        }
    }

    return root
}

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

func main() {
    // Example table
    //   Id  Name     ParentId 
    table := []Row{
        {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},
    }

    // Build tree
    root := buildTree(table)

    // Print tree
    printTree(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