'Coding has over 700 languages', '67% of programming jobs aren’t in the technology industry', 'Coding is behind almost everything that is powered by electricity', 'Knowing how to code is a major requirement for astronomers', 'The first computer didn’t use any electricity', 'Do you know there is a coding language named “Go“', 'Computer programming is one of the fastest-growing careers', 'Fortran (FORmula TRANslation) was the name of the first programming language', 'The first programmer was the daughter of a mad poet', 'Many programming languages share the same structure', 'Coding will soon be as important as reading', 'How many programmers does it take to change a light bulb? None, that’s a hardware problem', 'Why do Java developers wear glasses? Because they can’t C', 'Software and temples are much the same — first we build them, then we pray', 'An engineer will not call it a bug — it’s an undocumented feature', 'In a room full of top software designers, if two agree on the same thing, that’s a majority', 'C programmers never die. They are just cast into void', 'Knock, knock … Who’s there? … *very long pause* … Java', 'The best thing about a boolean is even if you are wrong, you are only off by a bit', 'Linux is only free if your time has no value', 'The computer was born to solve problems that did not exist before', 'Coding has over 700 languages', '67% of programming jobs aren’t in the technology industry', 'Coding is behind almost everything that is powered by electricity', 'Knowing how to code is a major requirement for astronomers', 'The first computer didn’t use any electricity', 'Do you know there is a coding language named “Go“', 'Computer programming is one of the fastest-growing careers', 'Fortran (FORmula TRANslation) was the name of the first programming language', 'The first programmer was the daughter of a mad poet', 'Many programming languages share the same structure', 'Coding will soon be as important as reading', 'How many programmers does it take to change a light bulb? None, that’s a hardware problem', 'Why do Java developers wear glasses? Because they can’t C', 'Software and temples are much the same — first we build them, then we pray', 'An engineer will not call it a bug — it’s an undocumented feature', 'In a room full of top software designers, if two agree on the same thing, that’s a majority', 'C programmers never die. They are just cast into void', 'Knock, knock … Who’s there? … *very long pause* … Java', 'The best thing about a boolean is even if you are wrong, you are only off by a bit', 'Linux is only free if your time has no value', 'The computer was born to solve problems that did not exist before',
Update appNew update is available. Click here to update.
Last Updated: Jun 30, 2023
Medium

Create a Balanced Binary Tree using leaf Nodes of a Binary Tree without using Extra Space

Introduction 

binary tree is a data arrangement in the form of a tree defined by nodes and edges, in which every node has at most two children. Let us learn about a balanced binary tree now. 

A balanced binary tree, also known as a height-balanced binary tree, is a special type of binary tree in which the height of left subtree and right subtree of any node differs maximum by 1. That is, the difference between the heights of left and right subtree is either 0 or 1. This property holds for every node in the tree if it is a height balanced tree. 

Create a Balanced Binary Tree using leaf Nodes of a Binary Tree without using Extra Space

In this task, we will be given a binary tree as input and will be needed to build a balanced binary tree using the leaf nodes of the input tree without using any additional space.

Let's see the below example to learn constructing a balanced binary tree from the leaf nodes of a binary tree without any extra space.

Problem Statement

Given, the root of a binary tree. Construct a balanced binary tree using the leaves of the input tree without using any extra space. Print the inorder traversal of the obtained tree.

Input

binary tree

Output

4 8 9 7

Explanation

The input tree is as follows

binary tree

We can observe that in the above tree, the leaf nodes are { 4, 8, 9, 7 }. If we construct a balanced binary tree using these nodes, we obtain the following tree- 

Balanced binary tree

If we write the inorder traversal of the above binary tree, we obtain 4 8 9 7, which is the output.

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

Approach

The approach to create a balanced binary tree from the leaves of a given binary tree without any extra space involves two recursive functions.

The first function generates a Doubly Linked List from the given binary tree's leaf nodes. It walks the tree depth-first, detaching the leaf nodes from the original tree and adding them to the doubly linked list. This function also maintains track of the list's head.

The second function employs the doubly linked list to construct a balanced binary tree. It constructs the left and right subtrees of each node iteratively, utilizing the first and final half nodes of the doubly linked list. The tree's root is the node in the middle of the list.

Let us see how we can implement this.

Algorithm 

Step 1: Create the Node class to generate binary tree nodes and linked list nodes with data, left, and right pointers.

Step 2: Call the get_leaves() function to obtain the leaves of the original binary tree in the form of a doubly linked list. Every time a leaf node is encountered, attach it to the head of the existing linked list and make it the new head. 

Step 3: Count the number of nodes in the obtained doubly linked list. 

Step 4: Define list_to_binary_tree(), a recursive function that takes the head pointer of the linked list and its size as input and generates a balanced binary tree from the provided doubly linked list. For this, take the first half nodes, and construct the left subtree. Construct the root with the next node in the DLL. For the remaining nodes of the DLL, call for the right subtree. Recursively repeat this process. 

Dry Run

1. The initial binary tree looks as follows. The leaf nodes are highlighted in red circles.

step 1: Initial binary tree

The first time get_leaves() is called, the value of the root is 1. It calls for its right child until a leaf node is encountered, which is 7. 

2. Once a leaf node is encountered, the right pointer of this leaf is set to point to the head of the existing linked list, which is initially NULL. Also, a null value is returned back to the most recent parent node, to detach this leaf from the original binary tree. The current node is made the head of doubly linked list.

Dry run step 2

3. Once the right child of any node is traversed, the left side is iterated over in the same manner. Hence the next encountered leaf node is 9. The right pointer is made to point to the head of the existing linked list, and the left pointer of the current head points to the current leaf node. Also, a null is returned to the most recent parent node.

Dry run step 3

4. Similarly, the same steps will be followed for the next leaves which are 8 and 4.

Dry run step 4 

Dry run step 5

5. Finally, the doubly linked list looks as follows

Dry run step 6

6. The list_to_binary_tree() function converts the given linked list into a binary tree. Every time, the central node is found, and a recursive call is made for all the nodes before it to construct the left subtree. The central node is then made the root and recursively a call is made for the remaining nodes to construct the right subtree.

Initially, 9 is the central node. A call is made for {4,8}. The leftmost node is 4. 

balanced binary tree

The next node is 8, hence 4 will be made the left child of 8. 

balanced binary tree

Since there are no more elements between 8 and 9, the right child of 8 will be NULL and 8 will be made the left child of 9.

balanced binary tree

Next, the right side of {9} contains only {7}. Hence {7} will be the right child of {9}. Thus, the obtained balanced binary tree looks as follows

Balanced binary tree

Hence we converted the given binary tree to a balanced binary tree without using any additional space. 

Let us now see the implementation of this effective approach. 

Implementation in C++

#include <bits/stdc++.h>
using namespace std;

// Class to define the nodes of linked list and tree
class Node{
    public:
        int value;
        Node *left;
        Node *right;

        // Constructor to initialize the value
        Node(int val)
        {
            this->left = NULL;
            this->right = NULL;
            this->value = val;
        }
};

/*
    Function to count the number of 
    nodes present in the linked list
*/ 
int count_of_nodes(Node *head){
    // Iterator to iterate over the linked list
    Node *iter = head;
    int count = 0;

    // Iterate till the end of linked list
    while (iter != NULL){
        count++;
        iter = iter->right;
    }
    return count;
}

/*
    Function to print the inorder traversal 
    of the obtained balanced binary tree
*/
void inorder(Node *root){
    if (root == NULL)
        return;

    inorder(root->left);
    cout << root->value << " ";
    inorder(root->right);
}

/*
    Function to obtain the leaf nodes
    of the original binary tree
*/
Node *get_leaves(Node *root, Node **head_of_DLL){
    if (root == NULL)
        return NULL;

    // If the current node is a leaf node
    if (root->left == NULL && root->right == NULL){
      
        root->right = *head_of_DLL;

        if (*head_of_DLL != NULL)
            (*head_of_DLL)->left = root;

        (*head_of_DLL) = root;

        return NULL;
    }

    /*
        If the current node is a non leaf node
        Call for the left and right subtrees
    */ 
    else{
        root->right = get_leaves(root->right, head_of_DLL);
        root->left = get_leaves(root->left, head_of_DLL);

        return root;
    }
}

/*
    Function to create balanced binary 
    tree from a doubly linked list 
*/
Node *list_to_binary_tree(Node **head_of_DLL, int number_of_nodes){
    // Base case
    if (number_of_nodes <= 0)
        return NULL;

    // Construct the left subtree using the first half nodes
    Node *left_subtree = list_to_binary_tree(head_of_DLL, number_of_nodes / 2);

    /*
        head_of_DLL now points to the middle element 
        of the linked list since first half has been 
        used to construct the left subtree.
        Now, construct the root of binary tree
    */
    Node *root = *head_of_DLL;

    // Attach the already constructed left subtree
    root->left = left_subtree;
    *head_of_DLL = (*head_of_DLL)->right;

    // Call for the right subtree
    root->right = list_to_binary_tree(head_of_DLL, number_of_nodes - number_of_nodes / 2 - 1);
    return root;
}

int main(){
    // Define a Null pointer as the head of doubly linked list
    Node *head = NULL;

    // Construct the original binary tree
    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);
    root->right->left = new Node(6);
    root->right->right = new Node(7);
    root->left->right->left = new Node(8);
    root->right->left->right = new Node(9);

    // Obtain the leaves of the above binary tree
    root = get_leaves(root, &head);

    // Count the number of obtained leaf nodes
    int nodes = count_of_nodes(head);

    // Construct the required balanced binary tree
    root = list_to_binary_tree(&head, nodes);

    // Print the inorder traversal of the above tree
    inorder(root);

    return 0;
}


Output

Cpp Output

Implementation in Java

// Importing required packages
import java.util.*;

// Class to define the nodes of linked list and tree
class Node {
    public int value;
    public Node left;
    public Node right;

    // Constructor to initialize the value
    public Node(int val) {
        this.left = null;
        this.right = null;
        this.value = val;
    }
}

public class Main {
    /*
        Function to count the number of 
        nodes present in the linked list
    */    
    public static int count_of_nodes(Node head) {
        // Iterator to iterate over the linked list
        Node iter = head;
        int count = 0;

        // Iterate till the end of linked list
        while (iter != null) {
            count++;
            iter = iter.right;
        }
        return count;
    }

    /*
        Function to print the inorder traversal 
        of the obtained balanced binary tree 
    */
    public static void inorder(Node root) {
        if (root == null)
            return;

        inorder(root.left);
        System.out.print(root.value + " ");
        inorder(root.right);
    }

    /*
        Function to obtain the leaf nodes
        of the original binary tree
    */    
    public static Node get_leaves(Node root, Node[] head_of_DLL) {
        if (root == null)
            return null;

        // If the current node is a leaf node
        if (root.left == null && root.right == null) {
            
            root.right = head_of_DLL[0];

            if (head_of_DLL[0] != null)
                head_of_DLL[0].left = root;
   
            head_of_DLL[0] = root;

            return null;
        }

        /* 
            If the current node is a non-leaf node,
            Call for the left and right subtrees
        */ 
        else {
            root.right = get_leaves(root.right, head_of_DLL);
            root.left = get_leaves(root.left, head_of_DLL);
            
            return root;
        }
    }

    /*
        Function to create balanced binary 
        tree from a doubly linked list 
    */
    public static Node list_to_binary_tree(Node[] head_of_DLL, int number_of_nodes) {
        // Base case
        if (number_of_nodes <= 0)
            return null;

        // Construct the left subtree using the first half nodes
        Node left_subtree = list_to_binary_tree(head_of_DLL, number_of_nodes / 2);
        
        /*
            Head_of_DLL now points to the middle element 
            of the linked list since first half has been 
            used to construct the left subtree.
            Now, construct the root of binary tree
        */ 
        Node root = head_of_DLL[0];

        // Attach the already constructed left subtree
        root.left = left_subtree;
        head_of_DLL[0] = head_of_DLL[0].right;

        // Call for the right subtree
        root.right = list_to_binary_tree(head_of_DLL, number_of_nodes - number_of_nodes / 2 - 1);
        
        return root;
    }
    
    public static void main(String[] args) {
        // Define a null pointer as the head of doubly linked list
        Node head = null;

        // Construct the original binary tree
        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);
        root.right.left = new Node(6);
        root.right.right = new Node(7);
        root.left.right.left = new Node(8);
        root.right.left.right = new Node(9);

        // Get the leaf nodes of the binary tree
        Node[] headRef = new Node[1];
        root = get_leaves(root, headRef);

        // Count the number of obtained leaf nodes
        int nodes = count_of_nodes(headRef[0]);

        // Construct the required balanced binary tree
        root = list_to_binary_tree(headRef, nodes);

        // Print the inorder traversal of the above tree
        inorder(root);
    }
}


Output

Java Output

Algorithm Complexity

Time Complexity: O(N)

In the above code, we have created four functions. Each of the four functions traverses to each node and takes O(1) time for each node. So, the overall time complexity will be O(N), where 'N' is the number of nodes in the binary tree.

Space Complexity: O(1) 

In the above code, to create a balanced binary tree using leaf nodes of a binary tree without any additional space the space complexity will be O(1) as we have used constant space.

Frequently Asked Questions

What is a balanced binary tree?

A balanced binary tree is a binary tree in which the height of the left subtree and right subtree of any node differs maximum by 1.

What is a doubly-linked list?

A doubly linked list is a linear data structure formed by linearly connected nodes. Each node has a value stored in it and the address of the previous and next nodes. 

What is a Symmetric Tree?

A symmetric tree is a tree where the left and the right subtrees are mirror images of each other for every node.

What is a partial BST?

A partial BST is a tree where for every node, the data of the left subtree is less than or equal to the root, and of the right subtree, it is greater than or equal to the root node.

When are two trees identical?

Two trees are identical if they have exactly the same configuration of the nodes, and the node values are also the same.

Conclusion

In this article, we discussed how to create a balanced binary tree using leaf nodes of a binary tree without using any extra space., its C++ and Java implementation, and its time and space complexity. If you want to solve more problems on tree data structure for practice, you can visit Coding Ninjas Studio.

You can visit more relatable articles on Coding Ninjas Studio-

Try practicing this question here on your own. Do share this blog with your friends. 

And many more on our platform Coding Ninjas Studio.Refer to our Guided Path to upskill yourself in DSACompetitive 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!

If you have just started your learning process and are looking for questions from tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problemsinterview experiences, and interview bundles for placement preparations.

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

Happy Learning, Ninjas!

Live masterclass