A height balanced binary tree is a binary tree in which the height of the left subtree and right subtree of any node does not differ by more than 1 and both the left and right subtree are also height balanced.
In this article, we will look into methods how to determine if given Binary trees are height-balanced
Examples: The tree on the left is a height balanced binary tree. Whereas the tree on the right is not a height balanced tree. Because the left subtree of the root has a height which is 2 more than the height of the right subtree.
Naive Approach: To check if a tree is height-balanced:
Get the height of left and right subtrees using dfs traversal. Return true if the difference between heights is not more than 1 and left and right subtrees are balanced, otherwise return false.
Below is the implementation of the above approach.
C++
/* CPP program to check if a tree is height-balanced or not */ #include <bits/stdc++.h> using namespace std; /* A binary tree node has data, pointer to left child and a pointer to right child */ class Node { public : int data; Node* left; Node* right; Node( int d) { int data = d; left = right = NULL; } }; // Function to calculate the height of a tree int height(Node* node) { // base case tree is empty if (node == NULL) return 0; // If tree is not empty then // height = 1 + max of left height // and right heights return 1 + max(height(node->left), height(node->right)); } // Returns true if binary tree // with root as root is height-balanced bool isBalanced(Node* root) { // for height of left subtree int lh; // for height of right subtree int rh; // If tree is empty then return true if (root == NULL) return 1; // Get the height of left and right sub trees lh = height(root->left); rh = height(root->right); if ( abs (lh - rh) <= 1 && isBalanced(root->left) && isBalanced(root->right)) return 1; // If we reach here then tree is not height-balanced return 0; } // Driver code int main() { 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->left->left->left = new Node(8); if (isBalanced(root)) cout << "Tree is balanced" ; else cout << "Tree is not balanced" ; return 0; } // This code is contributed by rathbhupendra |
C
/* C program to check if a tree is height-balanced or not */ #include <stdio.h> #include <stdlib.h> #define bool int /* A binary tree node has data, pointer to left child and a pointer to right child */ struct node { int data; struct node* left; struct node* right; }; /* Returns the height of a binary tree */ int height( struct node* node); /* Returns true if binary tree with root as root is * height-balanced */ bool isBalanced( struct node* root) { /* for height of left subtree */ int lh; /* for height of right subtree */ int rh; /* If tree is empty then return true */ if (root == NULL) return 1; /* Get the height of left and right sub trees */ lh = height(root->left); rh = height(root->right); if ( abs (lh - rh) <= 1 && isBalanced(root->left) && isBalanced(root->right)) return 1; /* If we reach here then tree is not height-balanced */ return 0; } /* UTILITY FUNCTIONS TO TEST isBalanced() FUNCTION */ /* returns maximum of two integers */ int max( int a, int b) { return (a >= b) ? a : b; } /* The function Compute the "height" of a tree. Height is the number of nodes along the longest path from the root node down to the farthest leaf node.*/ int height( struct node* node) { /* base case tree is empty */ if (node == NULL) return 0; /* If tree is not empty then height = 1 + max of left height and right heights */ return 1 + max(height(node->left), height(node->right)); } /* Helper function that allocates a new node with the given data and NULL left and right pointers. */ struct node* newNode( int data) { struct node* node = ( struct node*) malloc ( sizeof ( struct node)); node->data = data; node->left = NULL; node->right = NULL; return (node); } // Driver code int main() { struct node* root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5); root->left->left->left = newNode(8); if (isBalanced(root)) printf ( "Tree is balanced" ); else printf ( "Tree is not balanced" ); getchar (); return 0; } |
Java
/* Java program to determine if binary tree is height balanced or not */ /* A binary tree node has data, pointer to left child, and a pointer to right child */ class Node { int data; Node left, right; Node( int d) { data = d; left = right = null ; } } class BinaryTree { Node root; /* Returns true if binary tree with root as root is * height-balanced */ boolean isBalanced(Node node) { int lh; /* for height of left subtree */ int rh; /* for height of right subtree */ /* If tree is empty then return true */ if (node == null ) return true ; /* Get the height of left and right sub trees */ lh = height(node.left); rh = height(node.right); if (Math.abs(lh - rh) <= 1 && isBalanced(node.left) && isBalanced(node.right)) return true ; /* If we reach here then tree is not height-balanced */ return false ; } /* UTILITY FUNCTIONS TO TEST isBalanced() FUNCTION */ /* The function Compute the "height" of a tree. Height is the number of nodes along the longest path from the root node down to the farthest leaf node.*/ int height(Node node) { /* base case tree is empty */ if (node == null ) return 0 ; /* If tree is not empty then height = 1 + max of left height and right heights */ return 1 + Math.max(height(node.left), height(node.right)); } public static void main(String args[]) { BinaryTree tree = new BinaryTree(); tree.root = new Node( 1 ); tree.root.left = new Node( 2 ); tree.root.right = new Node( 3 ); tree.root.left.left = new Node( 4 ); tree.root.left.right = new Node( 5 ); tree.root.left.left.left = new Node( 8 ); if (tree.isBalanced(tree.root)) System.out.println( "Tree is balanced" ); else System.out.println( "Tree is not balanced" ); } } // This code has been contributed by Mayank // Jaiswal(mayank_24) |
Python3
""" Python3 program to check if a tree is height-balanced """ # A binary tree Node class Node: # Constructor to create a new Node def __init__( self , data): self .data = data self .left = None self .right = None # function to find height of binary tree def height(root): # base condition when binary tree is empty if root is None : return 0 return max (height(root.left), height(root.right)) + 1 # function to check if tree is height-balanced or not def isBalanced(root): # Base condition if root is None : return True # for left and right subtree height lh = height(root.left) rh = height(root.right) # allowed values for (lh - rh) are 1, -1, 0 if ( abs (lh - rh) < = 1 ) and isBalanced( root.left) is True and isBalanced(root.right) is True : return True # if we reach here means tree is not # height-balanced tree return False # Driver function to test the above function root = Node( 1 ) root.left = Node( 2 ) root.right = Node( 3 ) root.left.left = Node( 4 ) root.left.right = Node( 5 ) root.left.left.left = Node( 8 ) if isBalanced(root): print ( "Tree is balanced" ) else : print ( "Tree is not balanced" ) # This code is contributed by Shweta Singh |
C#
using System; /* C# program to determine if binary tree is height balanced or not */ /* A binary tree node has data, pointer to left child, and a pointer to right child */ public class Node { public int data; public Node left, right; public Node( int d) { data = d; left = right = null ; } } public class BinaryTree { public Node root; /* Returns true if binary tree with root as root is height-balanced */ public virtual bool isBalanced(Node node) { int lh; // for height of left subtree int rh; // for height of right subtree /* If tree is empty then return true */ if (node == null ) { return true ; } /* Get the height of left and right sub trees */ lh = height(node.left); rh = height(node.right); if (Math.Abs(lh - rh) <= 1 && isBalanced(node.left) && isBalanced(node.right)) { return true ; } /* If we reach here then tree is not height-balanced */ return false ; } /* UTILITY FUNCTIONS TO TEST isBalanced() FUNCTION */ /* The function Compute the "height" of a tree. Height is the number of nodes along the longest path from the root node down to the farthest leaf node.*/ public virtual int height(Node node) { /* base case tree is empty */ if (node == null ) { return 0; } /* If tree is not empty then height = 1 + max of left height and right heights */ return 1 + Math.Max(height(node.left), height(node.right)); } public static void Main( string [] args) { BinaryTree tree = new BinaryTree(); tree.root = new Node(1); tree.root.left = new Node(2); tree.root.right = new Node(3); tree.root.left.left = new Node(4); tree.root.left.right = new Node(5); tree.root.left.left.left = new Node(8); if (tree.isBalanced(tree.root)) { Console.WriteLine( "Tree is balanced" ); } else { Console.WriteLine( "Tree is not balanced" ); } } } // This code is contributed by Shrikant13 |
Javascript
<script> // JavaScript program to check if a tree is height-balanced // A binary tree Node class Node{ // Constructor to create a new Node constructor(data){ this .data = data this .left = null this .right = null } } // function to find height of binary tree function height(root){ // base condition when binary tree is empty if (root == null ) return 0 return Math.max(height(root.left), height(root.right)) + 1 } // function to check if tree is height-balanced or not function isBalanced(root){ // Base condition if (root == null ) return true // for left and right subtree height let lh = height(root.left) let rh = height(root.right) // allowed values for (lh - rh) are 1, -1, 0 if (Math.abs(lh - rh) <= 1 && isBalanced( root.left)== true && isBalanced( root.right) == true ) return true // if we reach here means tree is not // height-balanced tree return false } // Driver function to test the above function let 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.left.left.left = new Node(8) if (isBalanced(root)) document.write( "Tree is balanced" , "</br>" ) else document.write( "Tree is not balanced" , "</br>" ) // This code is contributed by ShinjanPatra </script> |
Tree is not balanced
Time Complexity: O(n^2) in case of full binary tree.
Auxiliary Space: O(n) space for call stack since using recursion
Efficient implementation: Above implementation can be optimized by
Calculating the height in the same recursion rather than calling a height() function separately.
- For each node make two recursion calls – one for left subtree and the other for the right subtree.
- Based on the heights returned from the recursion calls, decide if the subtree whose root is the current node is height-balanced or not.
- If it is balanced then return the height of that subtree. Otherwise, return -1 to denote that the subtree is not height-balanced.
Below is the implementation of the above approach.
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Structure of a tree node struct Node { int key; struct Node* left; struct Node* right; Node( int k) { key = k; left = right = NULL; } }; // Function to check if tree is height balanced int isBalanced(Node* root) { if (root == NULL) return 0; int lh = isBalanced(root->left); if (lh == -1) return -1; int rh = isBalanced(root->right); if (rh == -1) return -1; if ( abs (lh - rh) > 1) return -1; else return max(lh, rh) + 1; } // Driver code int main() { Node* root = new Node(10); root->left = new Node(5); root->right = new Node(30); root->right->left = new Node(15); root->right->right = new Node(20); if (isBalanced(root) > 0) cout << "Balanced" ; else cout << "Not Balanced" ; return 0; } |
C
// C program to check if a tree is height-balanced or not */ #include <stdio.h> #include <stdlib.h> #define bool int // Structure of a tree node struct node { int data; struct node* left; struct node* right; }; // Function to create a new tree Node struct node* newNode( int data) { struct node* node = ( struct node*) malloc ( sizeof ( struct node)); node->data = data; node->left = NULL; node->right = NULL; return (node); } // Functio to check if tree is height balanced int isBalanced( struct node* root) { if (root == NULL) return 0; int lh = isBalanced(root->left); if (lh == -1) return -1; int rh = isBalanced(root->right); if (rh == -1) return -1; if ( abs (lh - rh) > 1) return -1; else return lh > rh ? lh + 1 : rh + 1; } // Driver code int main() { int height = 0; struct node* root = newNode(10); root->left = newNode(5); root->right = newNode(30); root->right->left = newNode(15); root->right->right = newNode(20); if (isBalanced(root) > 0) printf ( "Balanced" ); else printf ( "Not Balanced" ); getchar (); return 0; } |
Java
// Java code to implement the approach import java.io.*; import java.lang.*; import java.util.*; // Class to define the tree node class Node { int key; Node left; Node right; Node( int k) { key = k; left = right = null ; } } class GFG { // Driver code public static void main(String args[]) { Node root = new Node( 10 ); root.left = new Node( 5 ); root.right = new Node( 30 ); root.right.left = new Node( 15 ); root.right.right = new Node( 20 ); if (isBalanced(root) > 0 ) System.out.print( "Balanced" ); else System.out.print( "Not Balanced" ); } // Function to check if tree is height balanced public static int isBalanced(Node root) { if (root == null ) return 0 ; int lh = isBalanced(root.left); if (lh == - 1 ) return - 1 ; int rh = isBalanced(root.right); if (rh == - 1 ) return - 1 ; if (Math.abs(lh - rh) > 1 ) return - 1 ; else return Math.max(lh, rh) + 1 ; } } |
Python3
""" Python3 program to check if a tree is height-balanced """ # A binary tree Node class Node: # Constructor to create a new Node def __init__( self , data): self .data = data self .left = None self .right = None # Function to check if tree is height-balanced or not def isBalanced(root): # Base condition if root is None : return True # Compute height of left subtree lh = isBalanced(root.left) # If left subtree is not balanced, # return 0 if lh = = 0 : return 0 # Do same thing for the right subtree rh = isBalanced(root.right) if rh = = 0 : return 0 # Allowed values for (lh - rh) are 1, -1, 0 if ( abs (lh - rh) > 1 ): return 0 # If we reach here means tree is # height-balanced tree, return height # in this case else : return max (lh, rh) + 1 # Driver code if __name__ = = '__main__' : root = Node( 10 ) root.left = Node( 5 ) root.right = Node( 30 ) root.right.left = Node( 15 ) root.right.right = Node( 20 ) if (isBalanced(root) = = 0 ): print ( "Not Balanced" ) else : print ( "Balanced" ) # This code is contributed by Shweta Singh |
C#
// C# code to implement the approach using System; // Class to define a binary tree node public class Node { public int data; public Node left, right; public Node( int d) { data = d; left = right = null ; } } public class BinaryTree { public Node root; // Function to check if tree is height balanced public virtual int isBalanced(Node root) { if (root == null ) return 0; int lh = isBalanced(root.left); if (lh == -1) return -1; int rh = isBalanced(root.right); if (rh == -1) return -1; if (lh > rh + 1 || rh > lh + 1) return -1; else return Math.Max(lh, rh) + 1; } // Driver code public static void Main( string [] args) { BinaryTree tree = new BinaryTree(); tree.root = new Node(10); tree.root.left = new Node(5); tree.root.right = new Node(30); tree.root.right.left = new Node(15); tree.root.right.right = new Node(20); if (tree.isBalanced(tree.root) > 0) { Console.WriteLine( "Balanced" ); } else { Console.WriteLine( "Not Balanced" ); } } } // This code is contributed by Shrikant13 |
Javascript
<script> // JavaScript program to check if Binary tree is height-balanced // Class to define a binary tree node class Node{ // Constructor to create node of // binary tree constructor(data){ this .data = data this .left = this .right = null } } // Function to check if the tree is height balanced function isBalanced(root) { if (root == null ) return 0; int lh = isBalanced(root.left); if (lh == -1) return -1; int rh = isBalanced(root.right); if (rh == -1) return -1; if (Math.abs(lh - rh) > 1) return -1; else return Math.max(lh, rh) + 1; } // Driver code let root = new Node(10) root.left = new Node(5) root.right = new Node(30) root.right.left = new Node(15) root.right.right = new Node(20) if (isBalanced(root) > 0) document.write( 'Balanced' , "</br>" ) else document.write( 'Not Balanced' , "</br>" ) // This code is contributed by shinjanpatra </script> |
Balanced
Time Complexity: O(n)
- Because we are only one dfs call and utilizing the height returned from that to determine the height balance, it is performing the task in linear time.
Auxiliary Space: O(n)
Using Pair:
The idea is simple instead of calling two recursive function ‘isBalanced’ and ‘height’ we can use a pair in which first value will represent that if any subtree is balanced or not and second value will represent the height of the every subtree in this way we can easily find that if tree is balanced or not.
Follow the steps below to implement the above idea:
- Define a helper function isBalancedfast that takes a root node as input and returns a pair of boolean and integer values representing whether the tree rooted at the given node is balanced and its height, respectively.
- Define the base case for the recursion: if the root node is NULL, return a pair with first set to true and second set to 0.
- Recursively call isBalancedfast on the left and right subtrees of the current node.
- Retrieve the boolean and integer values from the returned pairs and set them to leftAns, rightAns, leftHeight, and rightHeight.
- Calculate the height of the current node by taking the maximum height of its left and right subtrees and adding 1.
- Check if the absolute difference between the heights of the left and right subtrees is less than or equal to 1. If so, set diff to true; otherwise, set it to false.
- Set ans.first to true if leftAns, rightAns, and diff are all true; otherwise, set it to false.
- Set ans.second to the height of the current node.
- Return ans.
- Define a public function isBalanced that takes a root node as input and calls the isBalancedfast helper function on the root node.
- Return the first element of the pair returned by the isBalancedfast function. This represents whether the entire binary tree is balanced or not.
Below is the implementation of the above approach:
C++
//C++ code to implement the above approach #include <bits/stdc++.h> // using the standard namespace using namespace std; // defining the structure for tree nodes struct Node { int val; Node *left, *right; Node( int v) : val(v) , left(nullptr) , right(nullptr) { } }; // defining the Solution class to check if a binary tree is // balanced class Solution { // helper function to determine if a binary tree is // balanced pair< bool , int > isBalancedfast(Node* root) { // base case: if root is null, the tree is balanced // and has height 0 if (root == NULL) { pair< bool , int > p = make_pair( true , 0); return p; } // recursively call isBalancedfast function on left // and right subtrees pair< int , int > left = isBalancedfast(root->left); pair< int , int > right = isBalancedfast(root->right); // retrieve whether left and right subtrees are // balanced bool leftAns = left.first; bool rightAns = right.first; // check the difference in heights of left and right // subtrees bool diff = abs (left.second - right.second) <= 1; // create a pair to store the answer (whether the // tree is balanced) and its height pair< bool , int > ans; // set the height of the current node ans.second = max(left.second, right.second) + 1; // if both subtrees are balanced and their heights // differ by at most 1, the tree is balanced if (leftAns && rightAns && diff) { ans.first = true ; } // otherwise, the tree is not balanced else { ans.first = false ; } return ans; } public : // Function to check whether a binary tree is balanced // or not. bool isBalanced(Node* root) { return isBalancedfast(root).first; } }; //Driver Code int main() { // create a 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->left->left->left = new Node(8); // create an object of the Solution class Solution obj; // check if the binary tree is balanced using the // isBalanced function if (obj.isBalanced(root)) { cout << "The given binary tree is balanced." << endl; } else { cout << "The given binary tree is not balanced." << endl; } return 0; } //This code is contributed by Veerendra_Singh_Rajpoot |
C#
using System; // defining the structure for tree nodes public class Node { public int val; public Node left; public Node right; public Node( int v) { val = v; left = null ; right = null ; } } // defining the Solution class to check // if a binary tree is balanced public class Solution { // helper function to determine if a // binary tree is balanced public ( bool , int ) IsBalancedfast(Node root) { // base case: if root is null, // the tree is balanced // and has height 0 if (root == null ) { return ( true , 0); } // recursively call IsBalancedfas // t function on left & right subtrees var left = IsBalancedfast(root.left); var right = IsBalancedfast(root.right); // retrieve whether left and right // subtrees are balanced bool leftAns = left.Item1; bool rightAns = right.Item1; // check the difference in heights of // left and right subtrees bool diff = Math.Abs(left.Item2 - right.Item2) <= 1; // if both subtrees are balanced // and their heights differ by at most // 1, the tree is balanced if (leftAns && rightAns && diff) { return ( true , Math.Max(left.Item2, right.Item2) + 1); } // otherwise, the tree is not balanced else { return ( false , 0); } } // Function to check whether a binary // tree is balanced or not. public bool IsBalanced(Node root) { return IsBalancedfast(root).Item1; } } // Driver Code public class Program { public static void Main( string [] args) { // create a 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.left.left.left = new Node(8); // create an object of Solution class Solution obj = new Solution(); // check if the binary tree is // balanced using the // IsBalanced function if (obj.IsBalanced(root)) { Console.WriteLine( "The given binary tree is balanced." ); } else { Console.WriteLine( "The given binary tree is not balanced." ); } } } |
Java
// defining the structure for tree nodes class Node { int val; Node left, right; public Node( int v) { val = v; left = null ; right = null ; } } // defining the Solution class to check if a binary tree is balanced class Solution { // helper function to determine if a binary tree is balanced private Pair<Boolean, Integer> isBalancedfast(Node root) { // base case: if root is null, the tree is balanced and has height 0 if (root == null ) { Pair<Boolean, Integer> p = new Pair<>( true , 0 ); return p; } // recursively call isBalancedfast function on left and right subtrees Pair<Boolean, Integer> left = isBalancedfast(root.left); Pair<Boolean, Integer> right = isBalancedfast(root.right); // retrieve whether left and right subtrees are balanced boolean leftAns = left.first; boolean rightAns = right.first; // check the difference in heights of left and right subtrees boolean diff = Math.abs(left.second - right.second) <= 1 ; // create a pair to store the answer (whether the tree is balanced) and its height Pair<Boolean, Integer> ans = new Pair<>( false , Math.max(left.second, right.second) + 1 ); // if both subtrees are balanced and their heights differ by at most 1, the tree is balanced if (leftAns && rightAns && diff) { ans = new Pair<>( true , Math.max(left.second, right.second) + 1 ); } return ans; } // Function to check whether a binary tree is balanced or not. public boolean isBalanced(Node root) { return isBalancedfast(root).first; } } // Driver Code public class Main { public static void main(String[] args) { // create a 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.left.left.left = new Node( 8 ); // create an object of the Solution class Solution obj = new Solution(); // check if the binary tree is balanced using the isBalanced function if (obj.isBalanced(root)) { System.out.println( "The given binary tree is balanced." ); } else { System.out.println( "The given binary tree is not balanced." ); } } } |
Python3
# defining the structure for tree nodes class Node: def __init__( self , val): self .val = val self .left = None self .right = None # defining the Solution class to check if a binary tree is # balanced class Solution: # helper function to determine if a binary tree is # balanced def isBalancedfast( self , root): # base case: if root is None, the tree is balanced # and has height 0 if root is None : return True , 0 # recursively call isBalancedfast function on left # and right subtrees left = self .isBalancedfast(root.left) right = self .isBalancedfast(root.right) # retrieve whether left and right subtrees are # balanced leftAns = left[ 0 ] rightAns = right[ 0 ] # check the difference in heights of left and right # subtrees diff = abs (left[ 1 ] - right[ 1 ]) < = 1 # set the height of the current node height = max (left[ 1 ], right[ 1 ]) + 1 # if both subtrees are balanced and their heights # differ by at most 1, the tree is balanced if leftAns and rightAns and diff: return True , height # otherwise, the tree is not balanced else : return False , height # Function to check whether a binary tree is balanced # or not. def isBalanced( self , root): return self .isBalancedfast(root)[ 0 ] # create a binary tree root = Node( 1 ) root.left = Node( 2 ) root.right = Node( 3 ) root.left.left = Node( 4 ) root.left.right = Node( 5 ) root.left.left.left = Node( 8 ) # create an object of the Solution class obj = Solution() # check if the binary tree is balanced using the # isBalanced function if obj.isBalanced(root): print ( "The given binary tree is balanced." ) else : print ( "The given binary tree is not balanced." ) |
Javascript
// defining the structure for tree nodes class Node { constructor(val) { this .val = val; this .left = null ; this .right = null ; } } // defining the Solution class to check if a binary tree is // balanced class Solution { // helper function to determine if a binary tree is // balanced isBalancedfast(root) { // base case: if root is null, the tree is balanced // and has height 0 if (root == null ) { return [ true , 0]; } // recursively call isBalancedfast function on left // and right subtrees let left = this .isBalancedfast(root.left); let right = this .isBalancedfast(root.right); // retrieve whether left and right subtrees are // balanced let leftAns = left[0]; let rightAns = right[0]; // check the difference in heights of left and right // subtrees let diff = Math.abs(left[1] - right[1]) <= 1; // create an array to store the answer (whether the // tree is balanced) and its height let ans = []; // set the height of the current node ans[1] = Math.max(left[1], right[1]) + 1; // if both subtrees are balanced and their heights // differ by at most 1, the tree is balanced if (leftAns && rightAns && diff) { ans[0] = true ; } // otherwise, the tree is not balanced else { ans[0] = false ; } return ans; } // Function to check whether a binary tree is balanced // or not. isBalanced(root) { return this .isBalancedfast(root)[0]; } } // create a binary tree let 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.left.left.left = new Node(8); // create an object of the Solution class let obj = new Solution(); // check if the binary tree is balanced using the // isBalanced function if (obj.isBalanced(root)) { console.log( "The given binary tree is balanced." ); } else { console.log( "The given binary tree is not balanced." ); } |
The given binary tree is not balanced.
Time Complexity: O(N) , where N is the number of nodes present in the tree, This is Because every node of the tree is visited only ones.
Auxiliary Space: O(H) , where h is the height of the binary tree.
Asked in: Amazon, Belzabar, Goldman Sachs, InMobi, Intel, Microsoft, Paytm, Synopsys, Walmart, Zillious
Please write comments if you find any of the above codes/algorithms incorrect, or find other ways to solve the same problem.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!