'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',

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

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

Output

4 8 9 7

Explanation

The input tree is as follows

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-

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

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.

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.

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

5. Finally, the doubly linked list looks as follows

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.

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

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.

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

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

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

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-

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 problems, interview 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

What does it take to become Microsoft SDE.

by Pranav Malik, SDE2@Microsoft

28 Feb, 2024

01:30 PM

How to command high salaries as a software engineer.

by Pranav Malik, SDE2@Microsoft

23 Feb, 2024

01:30 PM

Case Study for Data Analytic roles. Insights & Interview Prep

by Alka Pandey, Data Scientist @ Unilever

26 Feb, 2024

01:30 PM

Job opportunities in data. Insights from Amazon Data Scientist

by Abhishek Soni, Data Scientist @ Amazon

21 Feb, 2024

01:30 PM

What does it take to become Microsoft SDE.

by Pranav Malik, SDE2@Microsoft

28 Feb, 2024

01:30 PM

How to command high salaries as a software engineer.