Tree Terminology Root Leaf Height Depth Level in DSA Go - Build from Scratch

Understanding Tree Terminology: Root, Leaf, Height, Depth, Level

📖 Scenario: Imagine you are organizing a family tree. Each person is a node. The oldest ancestor is the root. People with no children are leaves. You want to understand how far each person is from the oldest ancestor and how tall the family tree is.

🎯 Goal: You will build a simple tree structure in Go and learn to identify the root, leaves, height, depth, and level of nodes.

📋 What You'll Learn

Create a tree node struct with a value and children

Create a root node with specific children

Add a variable to track the height of the tree

Write a function to calculate the depth of a node

Print the root value, leaf nodes, tree height, and depth of a specific node

💡 Why This Matters

🌍 Real World

Trees are used to organize data hierarchically, like family trees, file systems, or company structures.

💼 Career

Understanding tree terminology and traversal is essential for software engineers working with data structures, databases, and algorithms.

1

Create the Tree Structure with Root and Children

Create a struct called Node with a field value of type string and a field children which is a slice of pointers to Node. Then create a variable root of type *Node with value set to "Grandparent" and two children nodes with values "Parent1" and "Parent2".

DSA Go

type Node struct {
    value string
    children []*Node
}

// Create root node with two children
// Your code here

Hint

Define the struct first, then create the root node with two children inside the main function.

2

Add More Children and a Height Variable

Add two children to the Parent1 node with values "Child1" and "Child2". Then create an integer variable called height and set it to 3 representing the height of the tree.

DSA Go

package main

type Node struct {
    value string
    children []*Node
}

func main() {
    root := &Node{
        value: "Grandparent",
        children: []*Node{
            {value: "Parent1"},
            {value: "Parent2"},
        },
    }
    // Add children to Parent1 and set height
    // Your code here
}

Hint

Find the Parent1 node inside the root's children and add children to it. Then create the height variable.

3

Write a Function to Calculate Depth of a Node

Write a function called depth that takes a pointer to Node, a target string, and a current int depth. It returns the depth of the node with the target value or -1 if not found. Use recursion to search children. Then call depth(root, "Child2", 0) and store the result in a variable called child2Depth.

DSA Go

package main

type Node struct {
    value string
    children []*Node
}

func depth(node *Node, target string, current int) int {
    // Your code here
}

func main() {
    root := &Node{
        value: "Grandparent",
        children: []*Node{
            {
                value: "Parent1",
                children: []*Node{
                    {value: "Child1"},
                    {value: "Child2"},
                },
            },
            {value: "Parent2"},
        },
    }
    height := 3
    // Call depth function for "Child2"
    // Your code here
}

Hint

Use recursion to check if the current node matches the target. If not, check each child increasing the depth count.

4

Print Root, Leaves, Height, and Depth of Child2

Print the root node's value with "Root: " prefix. Then print all leaf nodes (nodes with no children) with "Leaf: " prefix, one per line. Print the tree height with "Height: " prefix. Finally, print the depth of "Child2" with "Depth of Child2: " prefix. Use a helper function printLeaves that takes a *Node and prints all leaves.

DSA Go

package main

import "fmt"

type Node struct {
    value string
    children []*Node
}

func depth(node *Node, target string, current int) int {
    if node == nil {
        return -1
    }
    if node.value == target {
        return current
    }
    for _, child := range node.children {
        d := depth(child, target, current+1)
        if d != -1 {
            return d
        }
    }
    return -1
}

func printLeaves(node *Node) {
    // Your code here
}

func main() {
    root := &Node{
        value: "Grandparent",
        children: []*Node{
            {
                value: "Parent1",
                children: []*Node{
                    {value: "Child1"},
                    {value: "Child2"},
                },
            },
            {value: "Parent2"},
        },
    }
    height := 3
    child2Depth := depth(root, "Child2", 0)

    // Print root value
    // Print leaves
    // Print height
    // Print depth of Child2
    // Your code here
}

Hint

Use fmt.Println to print the root value, height, and depth. Use recursion in printLeaves to print all leaves.