Single rooted tree in Go

Single rooted tree in Go

Problem

Given 2 arbitrary integers X and N construct a tree such that the root has X child nodes, and each of the root’s children has N child nodes. Walk the graph touching each node only once and tracking the distance of each node from the root of the tree. For every node that has children, the parent node MUST BE visited first.

The total number of node visitations should match the following formula:


T = (X * N) + X + 1

Solution

package main

import (
	"fmt"
)

// main will build and walk the tree
func main() {
	fmt.Println("Building Tree")
	root := buildTree()
	fmt.Println("Walking Tree")
	root.walk()

}

// Total is a fun way to total how many nodes we have visited
var total = 1

// How many children for the root to thave
const rootsChildren = 3

// How many children for the root's children to have
const childrenChildren = 10

// node is a super simple node struct that will form the tree
type node struct {
	parent   *node
	children []*node
	depth    int
}

// buildTree will construct the tree for walking.
func buildTree() *node {
	var root &node
	root.addChildren(rootsChildren)
	for _, child := range root.children {
		child.addChildren(childrenChildren)
	}
	return root
}

// addChildren is a convenience to add an arbitrary number of children
func (n *node) addChildren(count int) {
	for i := 0; i < count; i++ {
		newChild := &node{
			parent: n,
			depth:  n.depth + 1,
		}
		n.children = append(n.children, newChild)
	}
}

// walk is a recursive function that calls itself for every child
func (n *node) walk() {
	n.visit()
	for _, child := range n.children {
		child.walk()
	}
}

// visit will get called on every node in the tree.
func (n *node) visit() {
	d := "└"
	for i := 0; i <= n.depth; i++ {
		d = d + "───"
	}
	fmt.Printf("%s Visiting node with address %p and parent %p Total (%d)\n", d, n, n.parent, total)
	total = total + 1
}

 

Execution Output


Building Tree
Walking Tree
└─── Visiting node with address 0x104401a0 and parent 0x0 Total (1)
└────── Visiting node with address 0x104401c0 and parent 0x104401a0 Total (2)
└───────── Visiting node with address 0x10440220 and parent 0x104401c0 Total (3)
└───────── Visiting node with address 0x10440240 and parent 0x104401c0 Total (4)
└───────── Visiting node with address 0x10440260 and parent 0x104401c0 Total (5)
└───────── Visiting node with address 0x10440280 and parent 0x104401c0 Total (6)
└───────── Visiting node with address 0x104402a0 and parent 0x104401c0 Total (7)
└───────── Visiting node with address 0x104402e0 and parent 0x104401c0 Total (8)
└───────── Visiting node with address 0x10440300 and parent 0x104401c0 Total (9)
└───────── Visiting node with address 0x10440320 and parent 0x104401c0 Total (10)
└───────── Visiting node with address 0x10440340 and parent 0x104401c0 Total (11)
└───────── Visiting node with address 0x10440360 and parent 0x104401c0 Total (12)
└────── Visiting node with address 0x104401e0 and parent 0x104401a0 Total (13)
└───────── Visiting node with address 0x10440380 and parent 0x104401e0 Total (14)
└───────── Visiting node with address 0x104403a0 and parent 0x104401e0 Total (15)
└───────── Visiting node with address 0x104403c0 and parent 0x104401e0 Total (16)
└───────── Visiting node with address 0x104403e0 and parent 0x104401e0 Total (17)
└───────── Visiting node with address 0x10440400 and parent 0x104401e0 Total (18)
└───────── Visiting node with address 0x10440440 and parent 0x104401e0 Total (19)
└───────── Visiting node with address 0x10440460 and parent 0x104401e0 Total (20)
└───────── Visiting node with address 0x10440480 and parent 0x104401e0 Total (21)
└───────── Visiting node with address 0x104404a0 and parent 0x104401e0 Total (22)
└───────── Visiting node with address 0x104404c0 and parent 0x104401e0 Total (23)
└────── Visiting node with address 0x10440200 and parent 0x104401a0 Total (24)
└───────── Visiting node with address 0x104404e0 and parent 0x10440200 Total (25)
└───────── Visiting node with address 0x10440500 and parent 0x10440200 Total (26)
└───────── Visiting node with address 0x10440520 and parent 0x10440200 Total (27)
└───────── Visiting node with address 0x10440540 and parent 0x10440200 Total (28)
└───────── Visiting node with address 0x10440560 and parent 0x10440200 Total (29)
└───────── Visiting node with address 0x104405a0 and parent 0x10440200 Total (30)
└───────── Visiting node with address 0x104405c0 and parent 0x10440200 Total (31)
└───────── Visiting node with address 0x104405e0 and parent 0x10440200 Total (32)
└───────── Visiting node with address 0x10440600 and parent 0x10440200 Total (33)
└───────── Visiting node with address 0x10440620 and parent 0x10440200 Total (34)

Try it out

You can run the code yourself in the Go playground.

Thanks!

Thank you for reading my article. As always, I appreciate any feedback from users. So let me know how we could be better.

Follow @kris-nova

LEAVE A COMMENT

0 comment