Count Height of a Binary Tree

Given a Binary tree, the task is to Count Height of a Binary Tree, which is defined as the number of edges from the root to the deepest node.

Code Flow for Count Height of a Binary Tree

• Base Case (Null Check):

  • If node is null, return 0. This indicates that an empty node has been reached, and its depth is 0.

• Recursive Case:

  • If the node is not null, recursively calls itself on the left and right children of the current node (node.left and node.right).

  • The height of the current node is calculated by taking the maximum height between the left and right subtrees using Math.max().

  • The result is then incremented by 1 to account for the edge between the current node and its child.

• Return Value:

  • The final height of the binary tree is returned, which is the maximum depth of the tree from the root to the deepest leaf 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 countTreeHeight(Node node) {
        if (Objects.isNull(node)) {
            System.out.println("BinaryTree.countTreeHeight node is null");
            return 0;
        }
        return Math.max(countTreeHeight(node.left), countTreeHeight(node.right)) + 1;
    }

    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.countTreeHeight(null), "Height 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.countTreeHeight(tree.root), "Height of a single node tree should be 1");
    }

    @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(3, BinaryTree.countTreeHeight(tree.root), "Height 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.countTreeHeight(tree.root), "Height 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(4, BinaryTree.countTreeHeight(tree.root), "Height 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.countTreeHeight(tree.root), "Height 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(3, BinaryTree.countTreeHeight(root), "Height of Balanced Tree should be correct");
    }

    @Test
    void testRightSkewedTree() {
        // Constructing the following tree:
        //          10
        //           \
        //            20
        //             \
        //              30
        //               \
        //                40
        //                 \
        //                  50
        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.countTreeHeight(root), "Height of Right Skewed should be correct");
    }

    @Test
    void testTreeWithDuplicateValues() {
        // Constructing the following tree:
        //          1
        //       /    \
        //      1       1
        //     / \     / \
        //    1   1   1   1
        Node root = new Node(1);
        root.left = new Node(1);
        root.right = new Node(1);
        root.left.left = new Node(1);
        root.left.right = new Node(1);
        root.right.left = new Node(1);
        root.right.right = new Node(1);
        assertEquals(3, BinaryTree.countTreeHeight(root), "Height of Tree with duplicate values.");
    }
}

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()
}

Complexity Analysis

Time Complexity

1. Time Complexity: O(n), where n is the number of nodes in the binary tree.

Space Complexity

1. Space Complexity: O(h), where h is the height of the tree. In the worst case, h can be O(n) (for a skewed tree), and in the best case, h is O(log n) (for a balanced tree).