Create Balanced Binary Tree using its Leaf Nodes without using extra space
Prerequisites: Binary Tree to Doubly Linked List
Given a Binary Tree, the task is to create a Balanced Binary Tree from all the leaf nodes of the given Binary Tree.
Examples:
Input:
Output: 7 8 5 9 10 Explanation: Required balanced binary tree will be:
Input:
Output: 13 21 29 7 15
Explanation: Required balanced binary tree is:
29
/ \
21 7
/ \
13 15
Approach:
Follow the steps below to solve the problem:
- Find all the leaf nodes in the given binary tree and create a doubly linked list using them.
- To create a Balanced Binary Tree from the above doubly linked list do the following:
- Find the middle node of the doubly linked list formed above and set it as a root node of the resultant tree.
- Recursively iterate for the left and right of the current middle node in the doubly linked list repeat the above steps until all nodes are covered.
- Print the newly created balanced binary tree.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Structure for Linked list and treeclass Node {public: int data; Node *left, *right;};// Function that returns the count of// nodes in the given linked listint countNodes(Node* head){ // Initialize count int count = 0; Node* temp = head; // Iterate till the end of LL while (temp) { temp = temp->right; // Increment the count count++; } // Return the final count return count;}// Function to return the root of// the newly created balanced binary// tree from the given doubly LLNode* sortedListToBSTRecur( Node** head_ref, int n){ // Base Case if (n <= 0) return NULL; // Recursively construct // the left subtree Node* left = sortedListToBSTRecur( head_ref, n / 2); // head_ref now refers to // middle node, make middle node // as root of BST Node* root = *head_ref; // Set pointer to left subtree root->left = left; // Change head pointer of // Linked List for parent // recursive calls *head_ref = (*head_ref)->right; // Recursively construct the // right subtree and link it // with root root->right = sortedListToBSTRecur( head_ref, n - n / 2 - 1); // Return the root of Balanced BT return root;}Node* sortedListToBST(Node* head){ /*Count the number of nodes in Linked List */ int n = countNodes(head); /* Construct BST */ return sortedListToBSTRecur( &head, n);}// Function to find the leaf nodes and// make the doubly linked list of// those nodesNode* extractLeafList(Node* root, Node** head_ref){ // Base cases if (root == NULL) return NULL; if (root->left == NULL && root->right == NULL) { // This node is added to doubly // linked list of leaves, and // set right pointer of this // node as previous head of DLL root->right = *head_ref; // Change left pointer // of previous head if (*head_ref != NULL) (*head_ref)->left = root; // Change head of linked list *head_ref = root; // Return new root return NULL; } // Recur for right & left subtrees root->right = extractLeafList(root->right, head_ref); root->left = extractLeafList(root->left, head_ref); // Return the root return root;}// Function to allocating new Node// int Binary TreeNode* newNode(int data){ Node* node = new Node(); node->data = data; node->left = NULL; node->right = NULL; return node;}// Function for inorder traversalvoid print(Node* root){ // If root is not NULL if (root != NULL) { print(root->left); // Print the root's data cout << root->data << " "; print(root->right); }}// Function to display nodes of DLLvoid printList(Node* head){ while (head) { // Print the data cout << head->data << " "; head = head->right; }}// Driver Codeint main(){ // Given Binary Tree Node* head = NULL; Node* root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5); root->right->right = newNode(6); root->left->left->left = newNode(7); root->left->left->right = newNode(8); root->right->right->left = newNode(9); root->right->right->right = newNode(10); // Function Call to extract leaf Node root = extractLeafList( root, &head); // Function Call to create Balanced BT root = sortedListToBST(head); // Print Inorder traversal New Balanced BT print(root); return 0;} |
Java
// Java program for // the above approachimport java.util.*;class GFG{// Structure for Linked // list and treestatic class Node { public int data; Node left, right;}; static Node head; // Function that returns the // count of nodes in the given // linked liststatic int countNodes(Node head){ // Initialize count int count = 0; Node temp = head; // Iterate till the // end of LL while (temp != null) { temp = temp.right; // Increment the count count++; } // Return the final count return count;}// Function to return the root of// the newly created balanced binary// tree from the given doubly LLstatic Node sortedListToBSTRecur(int n){ // Base Case if (n <= 0) return null; // Recursively construct // the left subtree Node left = sortedListToBSTRecur(n / 2); // head now refers to // middle node, make // middle node as root of BST Node root = head; // Set pointer to left subtree root.left = left; // Change head pointer of // Linked List for parent // recursive calls head = head.right; // Recursively construct the // right subtree and link it // with root root.right = sortedListToBSTRecur(n - n / 2 - 1); // Return the root // of Balanced BT return root;} static Node sortedListToBST(){ // Count the number of // nodes in Linked List int n = countNodes(head); // Construct BST return sortedListToBSTRecur(n);}// Function to find the leaf nodes and// make the doubly linked list of// those nodesstatic Node extractLeafList(Node root){ // Base cases if (root == null) return null; if (root.left == null && root.right == null) { // This node is added to doubly // linked list of leaves, and // set right pointer of this // node as previous head of DLL root.right = head; // Change left pointer // of previous head if (head != null) head.left = root; // Change head of linked list head = root; // Return new root return head; } // Recur for right & // left subtrees root.right = extractLeafList(root.right); root.left = extractLeafList(root.left); // Return the root return root;}// Function to allocating new // Node int Binary Treestatic Node newNode(int data){ Node node = new Node(); node.data = data; node.left = null; node.right = null; return node;}// Function for inorder traversalstatic void print(Node root){ // If root is not null if (root != null) { print(root.left); // Print the root's data System.out.print(root.data + " "); print(root.right); }}// Function to display nodes of DLLstatic void printList(Node head){ while (head != null) { // Print the data System.out.print(head.data + " "); head = head.right; }}// Driver Codepublic static void main(String[] args){ // Given Binary Tree head = null; Node root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(5); root.right.right = newNode(6); root.left.left.left = newNode(7); root.left.left.right = newNode(8); root.right.right.left = newNode(9); root.right.right.right = newNode(10); // Function Call to // extract leaf Node root = extractLeafList(root); // Function Call to create // Balanced BT root = sortedListToBST(); // Print Inorder traversal // New Balanced BT print(root);}}// This code is contributed by Amit Katiyar |
Python3
# Python3 program for the above approach# Structure for Linked list and treeclass newNode: def __init__(self, data): self.data = data self.left = None self.right = Nonehead = None# Function that returns the count of# nodes in the given linked listdef countNodes(head1): # Initialize count count = 0 temp = head1 # Iterate till the end of LL while (temp): temp = temp.right # Increment the count count += 1 # Return the final count return count# Function to return the root of# the newly created balanced binary# tree from the given doubly LLdef sortedListToBSTRecur(n): global head # Base Case if (n <= 0): return None # Recursively construct # the left subtree left = sortedListToBSTRecur(n // 2) # head_ref now refers to # middle node, make middle node # as root of BST root = head # Set pointer to left subtree root.left = left # Change head pointer of # Linked List for parent # recursive calls head = head.right # Recursively construct the # right subtree and link it # with root root.right = sortedListToBSTRecur(n - n // 2 - 1) # Return the root of Balanced BT return rootdef sortedListToBST(): global head # Count the number of nodes # in Linked List n = countNodes(head) # Construct BST return sortedListToBSTRecur(n)# Function to find the leaf nodes and# make the doubly linked list of# those nodesdef extractLeafList(root): global head # Base cases if (root == None): return None if (root.left == None and root.right == None): # This node is added to doubly # linked list of leaves, and # set right pointer of this # node as previous head of DLL root.right = head # Change left pointer # of previous head if (head != None): head.left = root # Change head of linked list head = root # Return new root return head # Recur for right & left subtrees root.right = extractLeafList(root.right) root.left = extractLeafList(root.left) # Return the root return root# Function for inorder traversaldef print1(root): # If root is not NULL if (root != None): print1(root.left) # Print the root's data print(root.data, end = " ") print1(root.right)# Function to display nodes of DLLdef printList(head): while(head): # Print the data print(head.data, end = " ") head = head.right# Driver Codeif __name__ == '__main__': # Given Binary Tree root = newNode(1) root.left = newNode(2) root.right = newNode(3) root.left.left = newNode(4) root.left.right = newNode(5) root.right.right = newNode(6) root.left.left.left = newNode(7) root.left.left.right = newNode(8) root.right.right.left = newNode(9) root.right.right.right = newNode(10) # Function Call to extract leaf Node root = extractLeafList(root) # Function Call to create Balanced BT root = sortedListToBST() # Print Inorder traversal New Balanced BT print1(root)# This code is contributed by ipg2016107 |
C#
// C# program for the above approachusing System;class GFG{// Structure for Linked // list and treepublic class Node { public int data; public Node left, right;}; static Node head; // Function that returns the // count of nodes in the given // linked liststatic int countNodes(Node head){ // Initialize count int count = 0; Node temp = head; // Iterate till the // end of LL while (temp != null) { temp = temp.right; // Increment the count count++; } // Return the readonly count return count;}// Function to return the root of// the newly created balanced binary// tree from the given doubly LLstatic Node sortedListToBSTRecur(int n){ // Base Case if (n <= 0) return null; // Recursively construct // the left subtree Node left = sortedListToBSTRecur(n / 2); // head now refers to // middle node, make // middle node as root of BST Node root = head; // Set pointer to left subtree root.left = left; // Change head pointer of // Linked List for parent // recursive calls head = head.right; // Recursively construct the // right subtree and link it // with root root.right = sortedListToBSTRecur(n - n / 2 - 1); // Return the root // of Balanced BT return root;} static Node sortedListToBST(){ // Count the number of // nodes in Linked List int n = countNodes(head); // Construct BST return sortedListToBSTRecur(n);}// Function to find the leaf nodes and// make the doubly linked list of// those nodesstatic Node extractLeafList(Node root){ // Base cases if (root == null) return null; if (root.left == null && root.right == null) { // This node is added to doubly // linked list of leaves, and // set right pointer of this // node as previous head of DLL root.right = head; // Change left pointer // of previous head if (head != null) head.left = root; // Change head of linked list head = root; // Return new root return head; } // Recur for right & // left subtrees root.right = extractLeafList( root.right); root.left = extractLeafList( root.left); // Return the root return root;}// Function to allocating new // Node int Binary Treestatic Node newNode(int data){ Node node = new Node(); node.data = data; node.left = null; node.right = null; return node;}// Function for inorder traversalstatic void print(Node root){ // If root is not null if (root != null) { print(root.left); // Print the root's data Console.Write(root.data + " "); print(root.right); }}// Function to display nodes of DLLstatic void printList(Node head){ while (head != null) { // Print the data Console.Write(head.data + " "); head = head.right; }}// Driver Codepublic static void Main(String[] args){ // Given Binary Tree head = null; Node root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(5); root.right.right = newNode(6); root.left.left.left = newNode(7); root.left.left.right = newNode(8); root.right.right.left = newNode(9); root.right.right.right = newNode(10); // Function call to // extract leaf Node root = extractLeafList(root); // Function call to create // Balanced BT root = sortedListToBST(); // Print Inorder traversal // New Balanced BT print(root);}}// This code is contributed by Amit Katiyar |
Javascript
<script> // Javascript program for the above approach // Structure for Linked // list and tree class Node { constructor(data) { this.left = null; this.right = null; this.data = data; } } let head; // Function that returns the // count of nodes in the given // linked list function countNodes(head) { // Initialize count let count = 0; let temp = head; // Iterate till the // end of LL while (temp != null) { temp = temp.right; // Increment the count count++; } // Return the final count return count; } // Function to return the root of // the newly created balanced binary // tree from the given doubly LL function sortedListToBSTRecur(n) { // Base Case if (n <= 0) return null; // Recursively construct // the left subtree let left = sortedListToBSTRecur(parseInt(n / 2, 10)); // head now refers to // middle node, make // middle node as root of BST let root = head; // Set pointer to left subtree root.left = left; // Change head pointer of // Linked List for parent // recursive calls head = head.right; // Recursively construct the // right subtree and link it // with root root.right = sortedListToBSTRecur(n - parseInt(n / 2, 10) - 1); // Return the root // of Balanced BT return root; } function sortedListToBST() { // Count the number of // nodes in Linked List let n = countNodes(head); // Construct BST return sortedListToBSTRecur(n); } // Function to find the leaf nodes and // make the doubly linked list of // those nodes function extractLeafList(root) { // Base cases if (root == null) return null; if (root.left == null && root.right == null) { // This node is added to doubly // linked list of leaves, and // set right pointer of this // node as previous head of DLL root.right = head; // Change left pointer // of previous head if (head != null) head.left = root; // Change head of linked list head = root; // Return new root return head; } // Recur for right & // left subtrees root.right = extractLeafList(root.right); root.left = extractLeafList(root.left); // Return the root return root; } // Function to allocating new // Node int Binary Tree function newNode(data) { let node = new Node(data); return node; } // Function for inorder traversal function print(root) { // If root is not null if (root != null) { print(root.left); // Print the root's data document.write(root.data + " "); print(root.right); } } // Function to display nodes of DLL function printList(head) { while (head != null) { // Print the data document.write(head.data + " "); head = head.right; } } // Given Binary Tree head = null; let root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(5); root.right.right = newNode(6); root.left.left.left = newNode(7); root.left.left.right = newNode(8); root.right.right.left = newNode(9); root.right.right.right = newNode(10); // Function Call to // extract leaf Node root = extractLeafList(root); // Function Call to create // Balanced BT root = sortedListToBST(); // Print Inorder traversal // New Balanced BT print(root); // This code is contributed by mukesh07.</script> |
Output:
7 8 5 9 10
Time Complexity: O(N), where N is the number of nodes in the given tree.
Auxiliary Space Complexity: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
