Print Data Between Given level of Binary Tree

Given a binary tree, implement a function to Print Data Between Given level of Binary Tree using Level Order Traversal.

Level Order Traversal or Breadth-First Search is one of the most common binary tree traversal techniques. Print the nodes between two specified levels lowLevel and highLevel.

Code Flow for Print Data Between Given Level of Binary Tree

If the root node is null (i.e., the tree is empty), the method returns immediately without doing anything.
A queue is initialized using a LinkedList. This queue will be used to perform level-order traversal (BFS) on the tree.
The root node is added to the queue to start the traversal.
The loop continues until all nodes in the queue are processed.
A node (temp) is removed from the front of the queue for processing.
The height of the node (temp.height) is stored in the variable i.
If the height i of the current node is between lowLevel and highLevel The node's data is printed.
If the left child exists, its height is set to i + 1, and it is added to the queue for further processing.
Similarly, if the right child exists, its height is set to i + 1, and it is added to the queue for further processing.

Summary of code

Level-order traversal (BFS) is used to visit nodes level by level.
The node's height is used to track its level in the tree.
Nodes that fall between the specified lowLevel and highLevel are printed.

Let's see the code now

package org.wesome.dsalgo;

import lombok.Data;

import java.util.LinkedList;
import java.util.Objects;
import java.util.Queue;

public class BinaryTree {
    Node root;

    public void printBetweenLevels(Node node, int lowLevel, int highLevel) {
        /*  If the root node is null i.e., the tree is empty, the method returns immediately without doing anything.  */
        if (Objects.isNull(node)) {
            return;
        }
        /*  A queue is initialized using a LinkedList. This queue will be used to perform level-order traversal (BFS) on the tree.  */
        Queue<Node> queue = new LinkedList<>();
        /*  The root node is added to the queue to start the traversal. */
        queue.add(node);
        while (!queue.isEmpty()) {
            /*  A node is removed from the front of the queue for processing.    */
            var curNode = queue.remove();
            int curHeight = curNode.height;
            /*  If the height of the current node is between lowLevel and highLevel, the node's data is printed.  */
            if (curHeight >= lowLevel && curHeight <= highLevel) {
                System.out.print(curNode.data + " ");
            }
            /*  If the left child exists, its height is set to i + 1, and it is added to the queue for further processing.  */
            if (Objects.nonNull(curNode.left)) {
                curNode.left.height = curHeight + 1;
                queue.add(curNode.left);
            }
            /*  if the right child exists, its height is set to i + 1, and it is added to the queue for further processing. */
            if (Objects.nonNull(curNode.right)) {
                curNode.right.height = curHeight + 1;
                queue.add(curNode.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;
    }
}

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

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

package org.wesome.dsalgo;

import org.junit.jupiter.api.Test;

public class BinaryTest {
    @Test
    void testEmptyTree() {
        // Test for an empty tree (null root)
        BinaryTree tree = new BinaryTree();
        tree.printBetweenLevels(null, 1, 1);
    }

    @Test
    void testSingleNodeTree() {
        // Test for a tree with a single node
        BinaryTree tree = new BinaryTree();
        tree.insert(10);
        tree.printBetweenLevels(tree.root, 1, 1);
    }

    @Test
    void testLevelsOutOfRange() {
        // test for Levels outside the valid range
        BinaryTree tree = new BinaryTree();
        tree.insert(10);
        tree.printBetweenLevels(tree.root, 5, 6);
    }

    @Test
    void testSingleLevel() {
        // Test for Single level print
        BinaryTree tree = new BinaryTree();
        tree.insert(10);
        tree.printBetweenLevels(tree.root, 1, 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);
        tree.printBetweenLevels(tree.root, 1, 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);
        tree.printBetweenLevels(tree.root, 2, 4);
    }

    @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);
        tree.printBetweenLevels(tree.root, 1, 3);
    }

    @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);
        }
        tree.printBetweenLevels(tree.root, 1, 1000);
    }


    @Test
    void testRightSkewedTree() {
        // Constructing the following tree:
        //          10
        //           \
        //            20
        //             \
        //              30
        //               \
        //                40
        //                 \
        //                  50
        BinaryTree tree = new BinaryTree();
        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);
        tree.printBetweenLevels(root, 1, 3);
    }

    @Test
    void testTreeWithDuplicateValues() {
        // Constructing the following tree:
        //          1
        //       /    \
        //      1       1
        //     / \     / \
        //    1   1   1   1
        BinaryTree tree = 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);
        tree.printBetweenLevels(root, 1, 3);
    }

    @Test
    void testTreeBinaryTreeValues() {
        // Constructing the following tree:
        //       1
        //      / \
        //     2   3
        //    / \
        //   4   5
        BinaryTree tree = new BinaryTree();
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        tree.printBetweenLevels(root, 1, 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

Time Complexity: O(n) — We visit each node once.

Space Complexity

Space Complexity: O(n) — The space used by the queue in the worst case.

Print Data Between Given level of Binary Tree

Code Flow for Print Data Between Given Level of Binary Tree

Summary of code

Complexity Analysis

Time Complexity

Space Complexity

follow us on