Height of Binary Tree in DSA Go - Build from Scratch

Height of Binary Tree

📖 Scenario: You are working on a program that analyzes family trees. Each person is a node, and their children are connected below them. You want to find out how tall the family tree is, meaning the longest chain from the oldest ancestor down to the youngest descendant.

🎯 Goal: Build a program to create a simple binary tree, then calculate and print its height.

📋 What You'll Learn

Create a binary tree node struct called Node with value, left, and right fields

Create a sample binary tree with exactly 5 nodes using Node

Create a function called height that calculates the height of the binary tree

Print the height of the binary tree

💡 Why This Matters

🌍 Real World

Binary trees are used in many applications like organizing data, searching quickly, and representing hierarchical information such as family trees or file systems.

💼 Career

Understanding binary trees and recursion is essential for software developers working with data structures, algorithms, and system design.

1

Create the binary tree nodes

Create a struct called Node with an int field called value and two pointers to Node called left and right. Then create a binary tree with 5 nodes: root node with value 1, root's left child with value 2, root's right child with value 3, left child's left child with value 4, and left child's right child with value 5.

DSA Go

// Define Node struct and create the binary tree nodes
// Your code here

Hint

Define the struct first, then create the root node and assign its children.

2

Create the height function signature

Create a function called height that takes a pointer to Node named node and returns an int. This function will calculate the height of the binary tree.

DSA Go

package main

type Node struct {
    value int
    left  *Node
    right *Node
}

func main() {
    root := &Node{value: 1}
    root.left = &Node{value: 2}
    root.right = &Node{value: 3}
    root.left.left = &Node{value: 4}
    root.left.right = &Node{value: 5}
}

// Create the height function below
// Your code here

Hint

Start the function by checking if the node is nil and return 0 in that case.

3

Implement the height calculation logic

Inside the height function, calculate the height of the left subtree by calling height(node.left) and store it in a variable called leftHeight. Similarly, calculate the height of the right subtree by calling height(node.right) and store it in rightHeight. Return the greater of leftHeight and rightHeight plus 1.

DSA Go

package main

type Node struct {
    value int
    left  *Node
    right *Node
}

func height(node *Node) int {
    if node == nil {
        return 0
    }
    // Calculate leftHeight and rightHeight
    // Return the greater plus 1
    // Your code here
}

func main() {
    root := &Node{value: 1}
    root.left = &Node{value: 2}
    root.right = &Node{value: 3}
    root.left.left = &Node{value: 4}
    root.left.right = &Node{value: 5}
}

Hint

Use recursion to get heights of left and right subtrees, then return the bigger one plus one.

4

Print the height of the binary tree

In the main function, call height(root) and print the result using fmt.Println. Import the fmt package at the top.

DSA Go

package main

import "fmt"

type Node struct {
    value int
    left  *Node
    right *Node
}

func height(node *Node) int {
    if node == nil {
        return 0
    }
    leftHeight := height(node.left)
    rightHeight := height(node.right)
    if leftHeight > rightHeight {
        return leftHeight + 1
    }
    return rightHeight + 1
}

func main() {
    root := &Node{value: 1}
    root.left = &Node{value: 2}
    root.right = &Node{value: 3}
    root.left.left = &Node{value: 4}
    root.left.right = &Node{value: 5}
    // Print the height of the tree
    // Your code here
}

Hint

Use fmt.Println(height(root)) to print the height.