Get Number of Nodes in a Binary Tree

Given a Binary Tree, Get Number of Nodes in a Binary Tree

This algorithm traverses the binary tree recursively and counts the nodes in each subtree, eventually returning the total number of nodes in the entire tree.

Code Flow for Get Number of Nodes in a Binary Tree

• Base Case (Null Check):

  • The method first checks if the node is null using Objects.isNull(node).

  • The method then returns 0, as there are no nodes to count in this branch of the tree.

• Recursive Case:

  • If the node is not null, the method returns 1 (for the current node itself), plus the result of recursively calling nodeCount(node.left) and nodeCount(node.right):

    • nodeCount(node.left) counts the nodes in the left subtree.

    • nodeCount(node.right) counts the nodes in the right subtree.

  • The results are added together, effectively counting the nodes in the left subtree, the right subtree, and the current node.

Let's see the code now

package org.wesome.dsalgo;

import lombok.Data;

import java.util.Objects;

@Data
class Node {
    int data;
    Node left, right;

    public Node(int data) {
        this.data = data;
        left = null;
        right = null;
    }
}

public class BinaryTree {
    Node root;

    public static int nodeCount(Node node) {
        if (Objects.isNull(node)) {
            System.out.println("BinaryTree.nodeCount node is null");
            return 0;
        }
        /*  If the node is not null, the method returns 1 for the current node itself, plus the result of recursively calling nodeCount for node.left and nodeCount for node.right */
        return 1 + nodeCount(node.left) + nodeCount(node.right);
    }

    void insert(int data) {
        System.out.println("BinarySearchTree.insert data = " + data);
        root = insert(root, data);
    }

    Node insert(Node root, int data) {
        if (Objects.isNull(root)) {
            Node tempNode = new Node(data);
            return tempNode;
        }
        if (data > root.data) {
            root.right = insert(root.right, data);
        } else {
            root.left = insert(root.left, data);
        }
        return root;
    }
}

package org.wesome.dsalgo;

import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.assertEquals;

public class BinaryTreeTest {
    @Test
    void testEmptyTree() {
        // Test for an empty tree (null root)
        assertEquals(0, BinaryTree.nodeCount(null), "Sum of an empty tree should be 0");
    }

    @Test
    void testSingleNodeTree() {
        // Test for a tree with a single node
        BinaryTree tree = new BinaryTree();
        tree.insert(10);
        assertEquals(1, BinaryTree.nodeCount(tree.root), "Sum of a single node tree should be the node's value");
    }

    @Test
    void testBalancedBinaryTree() {
        // Test for a balanced binary tree
        BinaryTree tree = new BinaryTree();
        tree.insert(10);
        tree.insert(5);
        tree.insert(15);
        tree.insert(2);
        tree.insert(7);
        tree.insert(12);
        tree.insert(18);
        assertEquals(7, BinaryTree.nodeCount(tree.root), "Sum of balanced binary tree nodes should be correct");
    }

    @Test
    void testUnbalancedBinaryTree() {
        // Test for an unbalanced binary tree (sorted order insertion creating a right-skewed tree)
        BinaryTree tree = new BinaryTree();
        tree.insert(10);
        tree.insert(20);
        tree.insert(30);
        tree.insert(40);
        tree.insert(50);
        assertEquals(5, BinaryTree.nodeCount(tree.root), "Sum of right-skewed tree nodes should be correct");
    }

    @Test
    void testTreeWithNegativeValues() {
        // Test for a tree with negative values
        BinaryTree tree = new BinaryTree();
        tree.insert(-5);
        tree.insert(-3);
        tree.insert(-2);
        tree.insert(-1);
        tree.insert(-7);
        tree.insert(-4);
        assertEquals(6, BinaryTree.nodeCount(tree.root), "Sum of tree with negative values should be correct");
    }

    @Test
    void testLargeTree() {
        // Test for a large tree with many nodes
        BinaryTree tree = new BinaryTree();
        for (int i = 1; i <= 1000; i++) {
            tree.insert(i);
        }
        assertEquals(1000, BinaryTree.nodeCount(tree.root), "Sum of large tree should be correct");
    }

    @Test
    void testBalancedTree() {
        Node root = new Node(10);
        root.left = new Node(5);
        root.right = new Node(15);
        root.left.left = new Node(2);
        root.left.right = new Node(7);
        root.right.left = new Node(12);
        root.right.right = new Node(18);
        assertEquals(7, BinaryTree.nodeCount(root), "Sum of Balanced Tree should be correct");

    }

    @Test
    void testRightSkewedTree() {
        Node root = new Node(10);
        root.right = new Node(20);
        root.right.right = new Node(30);
        root.right.right.right = new Node(40);
        root.right.right.right.right = new Node(50);
        assertEquals(5, BinaryTree.nodeCount(root), "Sum of Right Skewed Tree should be correct");
    }
}

plugins {
    id("java")
    id("io.freefair.lombok") version "8.13"
}

group = "org.wesome.dsalgo"
version = "1.0-SNAPSHOT"

repositories {
    mavenCentral()
}

dependencies {
    testImplementation(platform("org.junit:junit-bom:5.10.0"))
    testImplementation("org.junit.jupiter:junit-jupiter")
}

tasks.test {
    useJUnitPlatform()
}