Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem statement
1.2.
Examples
2.
Approach
2.1.
Algorithm
2.2.
Java code
2.2.1.
Complexity analysis
3.
Frequently Asked Questions
3.1.
What is the definition of a perfectly balanced tree?
3.2.
Is a complete binary tree a perfect binary tree?
3.3.
What is the height of a tree that is perfectly balanced?
4.
Conclusion
Last Updated: Mar 27, 2024
Medium

Print middle level of perfect binary tree without finding height

Author Ashish Sharma
0 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

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

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

What is the definition of a perfectly balanced tree?

If a tree is empty or the number of nodes in each subtree differs by no more than one, it is perfectly balanced. We know that searching the left or right subtree from any point will take the same amount of time in a perfectly balanced tree.

Is a complete binary tree a perfect binary tree?

All nodes in a full binary tree have either none or two children. All nodes up to level h could have two offspring in a complete binary tree of height h. A complete binary tree is referred to as a perfect binary tree.

What is the height of a tree that is perfectly balanced?

One approach to achieve this is to ensure that our trees are evenly spaced in height. If the left and right subtrees of any node are the same height, the tree is perfectly balanced. It is obvious that there are twice as many nodes at each level as there were at the preceding level, resulting in H = O. (logN).

Conclusion

In this article, we have discussed the perfect binary tree data structure in brief and how to print the middle level perfect binary tree without finding height with O(N) time complexity and O(N) space complexity. 

After reading about how to print the middle level of perfect binary tree without finding height., are you not feeling excited to read/explore more articles on the topic of file systems? Don't worry; Coding Ninjas has you covered. If you want to practice the questions on the binary tree then you can refer to these links tree traversalsum root to leafchildren sum propertytime required to burn the tree

 

Recommended problems -

 

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But suppose you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

Previous article
Print Levels of all Nodes in a Binary Tree
Next article
Print all nodes that are at distance k from a leaf node
Live masterclass