Trees

Build a Binary Tree

Create a fixed seven-node binary tree and render its shape.

Algorithm

The canonical tree is 4(2(1,3),6(5,7)), so this Go DSA implementation can be compared directly with the rest of the DSA track.

node links A node stores one value plus references to its left and right children.

Basic Implementation

basic.go
Replay: real traced execution (multi-file project)
package main

import (
    "fmt"
    "strings"
)

type Node struct { value int; left *Node; right *Node }
func render(node *Node) string {
    if node == nil { return "_" }
    if node.left == nil && node.right == nil { return fmt.Sprintf("%d", node.value) }
    return fmt.Sprintf("%d(%s,%s)", node.value, render(node.left), render(node.right))
}
func sampleTree() *Node {
    return &Node{4, &Node{2, &Node{1, nil, nil}, &Node{3, nil, nil}}, &Node{6, &Node{5, nil, nil}, &Node{7, nil, nil}}}
}
func listString(values []int) string {
    parts := []string{}
    for _, value := range values { parts = append(parts, fmt.Sprintf("%d", value)) }
    return "[" + strings.Join(parts, ", ") + "]"
}
func main() { fmt.Println(render(sampleTree())) }

  1. node ← 1, tree ← 1

    1package main
    values this step1node1tree

  2. node ← 3, tree ← 1, 3

    1package main
    values this step3node1, 3tree

  3. node ← 2, tree ← 2(1,3)

    1package main
    values this step2node2(1,3)tree

  4. node ← 5, tree ← 2(1,3), 5

    1package main
    values this step5node2(1,3), 5tree

  5. node ← 7, tree ← 2(1,3), 5, 7

    1package main
    values this step7node2(1,3), 5, 7tree

  6. node ← 6, tree ← 2(1,3), 6(5,7)

    1package main
    values this step6node2(1,3), 6(5,7)tree

  7. node ← 4, tree ← 4(2(1,3),6(5,7))

    1package main
    values this step4node4(2(1,3),6(5,7))tree

  8. stdout ← 4(2(1,3),6(5,7))

    10if node == nil { return "_" }11if node.left == nil && node.right == nil { return fmt.Sprintf("%d", node.value) }12return fmt.Sprintf("%d(%s,%s)", node.value, render(node.left), render(node.right))
    values this step4(2(1,3),6(5,7))stdout4(2(1,3),6(5,7))tree

Complexity

  • Time: O(n)
  • Space: O(n)

Implementation notes

  • Go represents each node as type Node struct { value int; left *Node; right *Node }, so the root and children are pointers and missing children are nil.
  • sampleTree() *Node returns one nested composite literal: &Node{4, &Node{2, ...}, &Node{6, ...}}. The address-taking literals allocate nodes whose lifetimes outlive the helper call; there is no manual free in this Go source.
  • Leaf nodes use &Node{1, nil, nil}, &Node{3, nil, nil}, &Node{5, nil, nil}, and &Node{7, nil, nil}. Parent literals wire those pointers into left and right fields.
  • The trace records construction bottom-up: nodes 1 and 3, then 2(1,3); nodes 5 and 7, then 6(5,7); finally root 4(2(1,3),6(5,7)).
  • render returns _ for a nil child, a bare value for leaves, and value(left,right) for interior nodes. fmt.Println(render(sampleTree())) prints 4(2(1,3),6(5,7)).