Get Sum of all Nodes in Binary Tree

Given a binary tree. Get Sum of all Nodes in Binary Tree. The algorithm starts from the root and recursively traverses the tree, summing up the values of all nodes in the tree. The base case handles empty nodes, ensuring that the recursion stops when reaching the leaf nodes' children.

Code Flow for Get Sum of all Nodes in Binary Tree

• Base Case: If the current node is null, return 0 because there is no value to add.

• Recursive Case: perform a depth-first traversal, also known as pre-order traversal of the binary tree. If the current node is not null, add the value of the current node to the sum of the left and right child nodes.

  • Recursively calculate the sum of the left subtree.

  • Recursively calculate the sum of the right subtree.

  • Return the sum of the current node's value, the left subtree sum, and the right subtree sum.

• Recursive Call: Perform the recursive calculation for each node, starting from the root of the tree.

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;

    /*  The getSumOfNodes method performs a depth-first traversal, also known as preorder traversal of the binary tree, and is summing up the data values of all nodes. The getSumOfNodes method will recursively call itself until it reaches null leaf nodes, at which point it returns 0.  */
    public static int getSumOfNodes(Node node) {
        if (Objects.isNull(node)) {
            System.out.println("BinaryTree.getSumOfNodes node is null");
            return 0;
        }
        /*  add the node data to the sums of the left and right child nodes and recursively call getSumOfNodes for the left child node and getSumOfNodes for the right child node.   */
        return node.data + getSumOfNodes(node.left) + getSumOfNodes(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.BeforeEach;
import org.junit.jupiter.api.Test;

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

public class BinaryTreeTest {

    private BinaryTree tree;

    @BeforeEach
    void setUp() {
        // Initialize the tree before each test
        tree = new BinaryTree();
    }

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

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

    @Test
    void testBalancedBinaryTree() {
        // Test for a balanced binary tree
        tree.insert(10);
        tree.insert(5);
        tree.insert(15);
        tree.insert(2);
        tree.insert(7);
        tree.insert(12);
        tree.insert(18);
        assertEquals(69, BinaryTree.getSumOfNodes(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)
        tree.insert(10);
        tree.insert(20);
        tree.insert(30);
        tree.insert(40);
        tree.insert(50);
        assertEquals(150, BinaryTree.getSumOfNodes(tree.root), "Sum of right-skewed tree nodes should be correct");
    }

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

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

    // Additional helper method for creating a balanced tree for testing purposes
    private Node createBalancedTree() {
        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);
        return root;
    }

    // Helper method to create a right-skewed tree (inserting in sorted order)
    private Node createRightSkewedTree() {
        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);
        return root;
    }
}

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