Print Data Level by Level of Binary Tree in Reverse Order

Given a Binary Tree, the task is to print Data Level by Level of Binary Tree in Reverse Order, with each level on a new line. 

In a level-wise traversal (also called breadth-first traversal), visit all the nodes at the current level before moving on to the next level. This differs from depth-first traversal, which explores as far as possible along one branch before backtracking.

Code Flow for Print Data Level by Level of Binary Tree in Reverse Order

Method : printLevelByLevel 

  • Purpose: This method prints the binary tree's nodes level by level (one level per line).

  • Base Case: If the node is null, it returns without printing anything (empty tree).

  • Calculate Tree Height:

    • Calls countTreeHeight(node) to find the height of the tree.

  • Iterate through Levels:

    • Loops through each level from treeHeight to 1.

    • For each level, it calls the helper method printLevelByLevel(node, level) to print the nodes at that level.

    • After printing all nodes at the current level, it prints a newline to separate levels.

Method : printLevelByLevel(Node node, int level)

  • Purpose: This is a helper method that prints nodes at a specific level.

  • Base Case:

    • If the node is null, return without printing.

  • When the desired level is reached:

    • If level == 1, it means the current node is at the desired level, so it prints the node's data.

  • Recursive Case:

    • Calls printLevelByLevel(node.left, level - 1) to check the left child at the next level.

    • Calls printLevelByLevel(node.right, level - 1) to check the right child at the next level.

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)) {
            return 0;
        }
        return Math.max(countTreeHeight(node.left), countTreeHeight(node.right)) + 1;
    }

    public static void printLevelByLevelReverseOrder(Node node) {
        if (Objects.isNull(node)) {
            return;
        }
        int treeHeight = countTreeHeight(node);
        for (int i = treeHeight; i >= 0; i--) {
            printLevelByLevel(node, i + 1);
            System.out.println();
        }
    }

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

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

    @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.printLevelByLevel(tree.root);
    }

    @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.printLevelByLevel(tree.root);
    }

    @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.printLevelByLevel(tree.root);
    }

    @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.printLevelByLevel(tree.root);
    }

    @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.printLevelByLevel(root);
    }

    @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.printLevelByLevel(root);
    }

    @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.printLevelByLevel(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()
}

Complexity Analysis

Time Complexity

O(n) (because each node is visited once during traversal and the height calculation).

Space Complexity

O(n) in the worst case (due to recursion stack depth in a skewed tree).

follow us on

YouTube IconLinkedIn Icon