Print Data at Given Level in Binary Tree

Given a Binary Tree, the task is to Print Data at Given Level in Binary Tree.

Code Flow for Print Data at Given Level in Binary Tree

• Base Case for Null Node:

  • if (Objects.isNull(node)):

    • Checks if the given node is null.

    • If the node is null, it prints a message ("BinaryTree.printAtLevel node is null") and returns, effectively stopping further processing for this branch of the tree.

• Base Case for Reaching Desired Level:

  • if (level == 1):

    • If the current level is 1, it means the current node is at the desired level.

    • It prints the data of the current node: System.out.println("BinaryTree.printAtLevel " + node.data);.

    • After printing the data, the method returns and does not process further.

• Recursive Calls for Left and Right Subtrees:

  • printAtLevel(node.left, level - 1);:

    • Recursively calls printAtLevel on the left child of the current node, reducing the level by 1.

  • printAtLevel(node.right, level - 1);:

    • Similarly, it calls printAtLevel on the right child of the current node, again reducing the level by 1.

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 void printAtLevel(Node node, int level) {
        if (Objects.isNull(node)) {
            System.out.println("BinaryTree.printAtLevel node is null");
            return;
        }
        /*  If the current level is 1, it means the current node is at the desired level.   */
        if (level == 1) {
            System.out.println("BinaryTree.printAtLevel " + node.data);
            return;
        }
        /*  Recursively calls printAtLevel on the left child of the current node, reducing the level by 1.  */
        printAtLevel(node.left, level - 1);
        /*  Recursively calls printAtLevel on the right child of the current node, reducing the level by 1.  */
        printAtLevel(node.right, 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;

public class BinaryTreeTest {

    @Test
    void testEmptyTree() {
        // Test for an empty tree (null root)
        BinaryTree.printAtLevel(null, 1);
    }

    @Test
    void testSingleNodeTree() {
        // Test for a tree with a single node
        BinaryTree tree = new BinaryTree();
        tree.insert(10);
        BinaryTree.printAtLevel(tree.root, 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);
        BinaryTree.printAtLevel(tree.root, 3);
    }

    @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);
        BinaryTree.printAtLevel(tree.root, 5);
    }

    @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);
        BinaryTree.printAtLevel(tree.root, 4);
    }

    @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);
        }
        BinaryTree.printAtLevel(tree.root, 999);
    }

    @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);
        BinaryTree.printAtLevel(root, 3);
    }

    @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);
        BinaryTree.printAtLevel(root, 5);
    }

    @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);
        BinaryTree.printAtLevel(root, 3);
    }
}

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(n) in the worst case (unbalanced tree) and O(log n) in the best case (balanced tree).