Print Level of a Node

Given a Binary Tree, the task is to find the Print Level of a Node in the Binary Tree, whereas the level of a node is defined as the number of edges from the root node to the target node. The root node is at level 0.

Code Flow for Print Level of a Node

• Base case check:

  • if (Objects.isNull(node)) { ... return 0; }

    • If the current node is null, it means you've reached the end of a branch (or the tree is empty).

    • The method returns 0, indicating the target node was not found on this path.

• Check if the current node matches the target data:

  • if (node.data == targetData) { return level; }

    • If the current node's data matches the targetData, it means you've found the node.

    • The method then returns the level of the node, which represents its depth in the tree.

• Recursive call for the left child:

  • int leftLevel = nodeLevel(node.left, targetData, level + 1);

    • The method recursively searches the left child of the current node, passing an incremented level value (because the left child is one level deeper).

    • The result of this recursive call is stored in leftLevel.

• If the left search was successful:

  • if (leftLevel != 0) { return leftLevel; }

    • If the left subtree search returns a non-zero value (i.e., the node was found), it immediately returns that leftLevel value, indicating the target node was found in the left subtree.

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 nodeLevel(Node node, int targetData, int level) {
        /*  If the current node is null, it means you've reached the end of a branch (or the tree is empty).    */
        if (Objects.isNull(node)) {
            System.out.println("BinaryTree.nodeCount node is null");
            return 0;
        }
        /*  If the current node's data matches the targetData, it means you've found the node, return the level of the node, which represents its depth in the tree.  */
        if (node.data == targetData) {
            return level;
        }
        /*  recursively searches the left child of the current node, with incremented level value because the left child is one level deeper.    */
        int leftLevel = nodeLevel(node.left, targetData, level + 1);

        /*  If the left subtree search returns a non-zero value i.e., indicating the target node was found in the left subtree, return the level  */
        if (leftLevel != 0) {
            return leftLevel;
        }

        /*  recursively searches the right child of the current node, with incremented level value because the right child is one level deeper.    */
        return nodeLevel(node.right, targetData, level + 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 {
    private static final int initialLevel = 1;

    @Test
    void testEmptyTree() {
        // Test for an empty tree (null root)
        assertEquals(0, BinaryTree.nodeLevel(null, 0, initialLevel), "Node level 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.nodeLevel(tree.root, 10, initialLevel), "Node level 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(3, BinaryTree.nodeLevel(tree.root, 18, initialLevel), "Node level of balanced binary tree nodes should be correct");
    }

    @Test
    void testTargetNotInTree() {
        // 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(0, BinaryTree.nodeLevel(tree.root, 20, initialLevel), "Node level of invalid data should not be found");
    }

    @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.nodeLevel(tree.root, 50, initialLevel), "Node level 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(3, BinaryTree.nodeLevel(tree.root, -4, initialLevel), "Node level 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.nodeLevel(tree.root, 1000, initialLevel), "Node level 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.nodeLevel(root, 18, initialLevel), "Node level 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.nodeLevel(root, 50, initialLevel), "Node level of Right Skewed Tree should be correct");
    }

    @Test
    void testTreeWithDuplicateValues() {
        // Constructing the following tree:
        //          1
        //       /    \
        //      1       1
        //     / \     / \
        //    1   1   1   1

        BinaryTree binaryTree = new BinaryTree();
        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(1, BinaryTree.nodeLevel(root, 1, initialLevel), "Node level 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()
}

Complexity Analysis

Time Complexity

O(n) where n is the total number of nodes in the trees.

Space Complexity

O(h) where h is the height of the tree (can be as bad as O(n) for a skewed tree or O(log n) for a balanced tree).