## 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);
}
}
```

**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).