Print middle level of perfect binary tree without finding height

Introduction

In this article, we will understand the perfect binary tree data structure in brief, and we will discuss a problem on how to print the middle level of perfect binary tree without finding height. A perfect binary tree is one in which every internal node has exactly two child nodes, and all leaf nodes are at the same level. The maximum number of leaf nodes is calculated using the formula 2h or (n + 1)/2.

                                                                                   Perfect binary tree

Here the middle level of perfect binary tree is: {21,22}

Problem statement

We are given a perfect binary tree, we have to print the nodes of the middle level of a perfect binary tree without determining its height.

Examples

 Input

Output

middle_level[] = {21, 33}

In the above example, we have seen that the nodes having values equal to 21 and 31  are the middle level of perfect binary tree.

Input

Output

middle_level[] = {15, 25}

In the above example, we have seen that the nodes having values equal to 15 and 25 are the middle level of perfect binary tree.

Approach

In the given problem, we are will print the middle level of the perfect binary tree. To do so, we will use two pointers: left and right. These pointers are not null. we will be incrementing the left pointer by 2 and right pointer by 1 and trying to find if the left pointer reaches a leaf node or not. If yes then print the values to the right pointer. then taking a recursive call for the above conditions by building a function.

Algorithm

• We will first Declare a left and a right pointer in each route of a tree.
• We will then increment the left pointer by 2.
• We will then increment the right pointer by 1.
• Now we will check whether the left pointer reaches the leaf node, if it has reached then we will print the node value at the right pointer.
• We will repeat the above step by making recursive calls.

Java code

// java program to print middle level of perfect binary tree without finding height
import java.util.*;
// Tree node
class Node
{
public
    char VALUE;
public
    Node left;
public
    Node right;
public
    Node(char val)
    {
        this.left = null;
        this.right = null;
        this.VALUE = val;
    }
}

public class leafnode3
{
private
    static void leafnode3LevelUtil(Node X, Node Y)
    {

        // Base case
        if (X == null || Y == null)
            return;

        // Checking y left and right child if they are null or not
        if ((Y.left == null) && (Y.right == null))
        {
            System.out.print(X.VALUE + " ");
            return;
        }

        // recursive calls
        if (Y.left.left == null)
        {
            leafnode3LevelUtil(X.left, Y.left);
            leafnode3LevelUtil(X.right, Y.left);
        }
        else
        {
            leafnode3LevelUtil(X.left, Y.left.left);
            leafnode3LevelUtil(X.right, Y.left.left);
        }
    }

    // Driver code
public
    static void main(String[] args)
    {
        // taking the input from the users 
        Scanner sc = new Scanner(System.in);

        //assigning values to the left child and right child of the nodes
        System.out.println("Enter the root element of the tree");
        Node R1 = new Node(sc.next().charAt(0));
        System.out.println("Enter the root left element of the tree");
        Node R2 = new Node(sc.next().charAt(0));
        System.out.println("Enter the root right element of the tree");
        Node R3 = new Node(sc.next().charAt(0));
        System.out.println("Enter the root left left element of the tree");
        Node R4 = new Node(sc.next().charAt(0));
        System.out.println("Enter the root left right element of the tree");
        Node R5 = new Node(sc.next().charAt(0));
        System.out.println("Enter the root right left element of the tree");
        Node R6 = new Node(sc.next().charAt(0));
        System.out.println("Enter the root right right element of the tree");
        Node R7 = new Node(sc.next().charAt(0));
        
        // printing the middle level of perfect binary tree without finding height
        System.out.println("\nprinting the middle element of a perfect binary tree without finding height");
        R1.left = R2;
        R1.right = R3;
        R2.left = R4;
        R3.left = R6;
        R2.right = R5;
        R3.right = R7;
        leafnode3LevelUtil(R1, R1);
    }
}

You can also try this code with Online Java Compiler

Run Code

Output

Complexity analysis

Time complexity

O(N), since we are performing the inorder traversal to find the middle level of the binary tree where N is the number of nodes.

Space complexity

O(1), since we are not storing nodes but using only two pointers to find the middle level of perfect binary tree therefore the space complexity would be O(1).