Count Total Nodes in Binary Tree in DSA Go - Build from Scratch

Count Total Nodes in Binary Tree

📖 Scenario: Imagine you are working with a family tree application. Each person is a node in a binary tree, where each node can have up to two children (left and right). You want to find out how many people (nodes) are in the family tree.

🎯 Goal: You will build a simple binary tree in Go and write a function to count the total number of nodes in the tree.

📋 What You'll Learn

Create a binary tree with exactly 5 nodes using a struct called Node

Add a variable called root that points to the root node of the tree

Write a recursive function called countNodes that returns the total number of nodes in the tree

Print the total number of nodes using fmt.Println

💡 Why This Matters

🌍 Real World

Counting nodes in a tree is useful in many applications like file systems, organizational charts, and family trees.

💼 Career

Understanding tree traversal and recursion is essential for software engineering roles involving data structures and algorithms.

1

Create the Binary Tree Structure and Nodes

Create a struct called Node with two fields: left and right of type *Node. Then create 5 nodes named node1 to node5. Connect them to form this tree:

node1 is root
node1.left = node2
node1.right = node3
node2.left = node4
node2.right = node5

Finally, create a variable called root that points to node1.

DSA Go

package main

import "fmt"

type Node struct {
    left  *Node
    right *Node
}

func main() {
    // Create nodes node1 to node5
    // Connect nodes as described
    // Create root pointing to node1
    // Your code here
}

Hint

Define the Node struct first. Then create each node using &Node{}. Connect the nodes by assigning the left and right fields. Finally, set root to point to node1.

2

Add a Helper Function to Count Nodes

Create a function called countNodes that takes a parameter node of type *Node and returns an int. This function will be used to count nodes recursively. For now, just add the function signature and return 0 inside the function.

DSA Go

package main

import "fmt"

type Node struct {
    left  *Node
    right *Node
}

func countNodes(node *Node) int {
    // Your code here
    return 0
}

func main() {
    node1 := &Node{}
    node2 := &Node{}
    node3 := &Node{}
    node4 := &Node{}
    node5 := &Node{}

    node1.left = node2
    node1.right = node3
    node2.left = node4
    node2.right = node5

    root := node1

    _ = root
}

Hint

Define the function countNodes with parameter node *Node and return type int. For now, just return 0 to complete the function.

3

Implement Recursive Logic to Count Nodes

Inside the countNodes function, write code to count nodes recursively. If node is nil, return 0. Otherwise, return 1 plus the count of nodes in the left subtree plus the count of nodes in the right subtree. Use countNodes(node.left) and countNodes(node.right) for recursion.

DSA Go

package main

import "fmt"

type Node struct {
    left  *Node
    right *Node
}

func countNodes(node *Node) int {
    if node == nil {
        // Your code here
    }
    // Your code here
}

func main() {
    node1 := &Node{}
    node2 := &Node{}
    node3 := &Node{}
    node4 := &Node{}
    node5 := &Node{}

    node1.left = node2
    node1.right = node3
    node2.left = node4
    node2.right = node5

    root := node1

    _ = root
}

Hint

Check if node is nil. If yes, return 0. Otherwise, return 1 plus recursive calls to countNodes on node.left and node.right.

4

Print the Total Number of Nodes

In the main function, call countNodes with root as argument and print the result using fmt.Println.

DSA Go

package main

import "fmt"

type Node struct {
    left  *Node
    right *Node
}

func countNodes(node *Node) int {
    if node == nil {
        return 0
    }
    return 1 + countNodes(node.left) + countNodes(node.right)
}

func main() {
    node1 := &Node{}
    node2 := &Node{}
    node3 := &Node{}
    node4 := &Node{}
    node5 := &Node{}

    node1.left = node2
    node1.right = node3
    node2.left = node4
    node2.right = node5

    root := node1

    // Your code here
}

Hint

Call countNodes(root) and print the result with fmt.Println.