- Problem Statement<\/a><\/li>
- Sample Test Cases :<\/strong><\/a><\/li><\/ul>
- Approach 1: Naive<\/a><\/li>
- C++ Code<\/a><\/li>
- Java Code<\/a><\/li>
- Python Code<\/a><\/li><\/ul>
- Approach 2: Optimal<\/a><\/li>
- C++ Code<\/a><\/li>
- Java Code<\/a><\/li>
- Python Code<\/a><\/li><\/ul>
- Practice Problem:<\/a><\/li>
- FAQs<\/a><\/li>
- Q.1: In what other types of trees is the concept of balancing used?<\/a><\/li>
- Q.2: What is the time complexity of the depth function in the naive approach?<\/a><\/li><\/ul><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n
Problem Statement<\/h2>\n\n\n\n
Given a binary tree, determine if is height-balanced.<\/p>\n\n\n\n
Height-Balanced: <\/strong>A binary tree is said to be height-balanced if the left and right subtrees of every node differ in height by no more than 1.<\/p>\n\n\n\n
Sample Test Cases :<\/strong><\/span><\/h6>\n\n\n\n
Input 1:<\/strong><\/p>\n\n\n\n
<\/figure>\n\n\n\n
Output 1:<\/strong><\/p>\n\n\n\n
True<\/p>\n\n\n\n
Explanation 1:<\/em><\/strong><\/p>\n\n\n\n
For every node in the tree, the height of the left and right subtree for that node differs by at most 1.<\/p>\n\n\n\n
Input 2:<\/strong><\/p>\n\n\n\n
Output 2:<\/strong><\/p>\n\n\n\n
False<\/p>\n\n\n\n
Explanation 2:<\/strong><\/p>\n\n\n\n
For node 1, the difference between the heights of the left and right subtree exceeds 1.<\/p>\n\n\n\n
Approach 1: Naive<\/h2>\n\n\n\n
We can solve this problem naively by using a recursive approach<\/strong>. The approach is as follows:<\/p>\n\n\n\n
- For each node, calculate the heights of the left and right subtrees of that node.<\/li>
- If the difference between heights is greater than 1, return false.<\/li>
- Else recursively check if the left and right nodes of the original node are also height-balanced.<\/li><\/ul>\n\n\n\n
Code \/ Implementation:<\/strong><\/p>\n\n\n\n
C++ Code<\/span><\/h3>\n\n\n\n
\/**\n * Definition for a binary tree node.\n * struct TreeNode {\n * int val;\n * TreeNode *left;\n * TreeNode *right;\n * TreeNode() : val(0), left(nullptr), right(nullptr) {}\n * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}\n * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}\n * };\n *\/\nclass Solution {\n public:\n int depth(TreeNode * root) {\n if (root == NULL) {\n return 0;\n }\n return max(depth(root -> left), depth(root -> right)) + 1;\n }\n bool isBalanced(TreeNode * root) {\n if (root == NULL) {\n return true;\n }\n int leftHeight = depth(root -> left);\n int rightHeight = depth(root -> right);\n if (abs(leftHeight - rightHeight) <= 1 && isBalanced(root -> left) && isBalanced(root -> right)) {\n return true;\n } else {\n return false;\n }\n }\n};<\/pre>\n\n\n\nJava Code<\/span><\/h3>\n\n\n\n
\/**\n * Definition for a binary tree node.\n * public class TreeNode {\n * int val;\n * TreeNode left;\n * TreeNode right;\n * TreeNode() {}\n * TreeNode(int val) { this.val = val; }\n * TreeNode(int val, TreeNode left, TreeNode right) {\n * this.val = val;\n * this.left = left;\n * this.right = right;\n * }\n * }\n *\/\nclass Solution {\n public int depth(TreeNode root) {\n if (root == null) {\n return 0;\n }\n return Math.max(depth(root.left), depth(root.right)) + 1;\n }\n public boolean isBalanced(TreeNode root) {\n if (root == null) {\n return true;\n }\n int leftHeight = depth(root.left);\n int rightHeight = depth(root.right);\n if (Math.abs(leftHeight - rightHeight) <= 1 && isBalanced(root.left) && isBalanced(root.right)) {\n return true;\n } else {\n return false;\n }\n }\n}<\/pre>\n\n\n\nPython Code<\/span><\/h3>\n\n\n\n
# Definition for a binary tree node.\n# class TreeNode(object):\n# def __init__(self, val=0, left=None, right=None):\n# self.val = val\n# self.left = left\n# self.right = right\nclass Solution(object):\n def depth(self, root):\n if root is None:\n return 0\n else:\n return max(self.depth(root.left), self.depth(root.right)) + 1\n\n def isBalanced(self, root):\n \"\"\"\n :type root: TreeNode\n :rtype: bool\n \"\"\"\n if root is None:\n return True\n leftHeight = self.depth(root.left)\n rightHeight = self.depth(root.right)\n if (\n abs(leftHeight - rightHeight) <= 1\n and self.isBalanced(root.left)\n and self.isBalanced(root.right)\n ):\n return True\n else:\n return False<\/pre>\n\n\n\n
Complexity Analysis:<\/strong><\/p>\n\n\n\n
- Time Complexity: O(n * n)<\/li>
- Space Complexity: O(1)<\/li><\/ul>\n\n\n\n
Approach 2: Optimal<\/h2>\n\n\n\n
The optimal approach is the same as the naive approach, but we can optimize the complexity by calculating the height of the subtrees of each node, in the same recursive function call, rather than calling a separate function to calculate the height of subtrees for each node.<\/p>\n\n\n\n
Since the recursion progresses in a bottom-up<\/strong> manner, the heights of the subtree of the children can be used to compute the heights of the subtree of the current node using the relation,<\/p>\n\n\n\n
- Height of current node = max(height of left subtree, height of right subtree) + 1.<\/li><\/ul>\n\n\n\n
Code<\/strong> Implementation:<\/strong><\/p>\n\n\n\n
C++ Code<\/h3>\n\n\n\n
\/**\n * Definition for a binary tree node.\n * struct TreeNode {\n * int val;\n * TreeNode *left;\n * TreeNode *right;\n * TreeNode() : val(0), left(nullptr), right(nullptr) {}\n * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}\n * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}\n * };\n *\/\nclass Solution {\n public:\n int check(TreeNode * root, bool & isBalanced) {\n if (root == NULL) {\n return 0;\n }\n int leftDepth = check(root -> left, isBalanced);\n int rightDepth = check(root -> right, isBalanced);\n if (abs(leftDepth - rightDepth) > 1) {\n isBalanced = false;\n }\n return max(leftDepth, rightDepth) + 1;\n }\n bool isBalanced(TreeNode * root) {\n bool bal = true;\n check(root, bal);\n return bal;\n }\n};<\/pre>\n\n\n\nJava Code<\/h3>\n\n\n\n
\/**\n * Definition for a binary tree node.\n * public class TreeNode {\n * int val;\n * TreeNode left;\n * TreeNode right;\n * TreeNode() {}\n * TreeNode(int val) { this.val = val; }\n * TreeNode(int val, TreeNode left, TreeNode right) {\n * this.val = val;\n * this.left = left;\n * this.right = right;\n * }\n * }\n *\/\nclass Solution {\n boolean isBalanced = false;\n public int check(TreeNode root) {\n if (root == null) {\n return 0;\n }\n int leftDepth = check(root.left);\n int rightDepth = check(root.right);\n if (Math.abs(leftDepth - rightDepth) > 1) {\n isBalanced = false;\n }\n return Math.max(leftDepth, rightDepth) + 1;\n }\n public boolean isBalanced(TreeNode root) {\n isBalanced = true;\n check(root);\n return isBalanced;\n }\n}<\/pre>\n\n\n\nPython Code<\/h3>\n\n\n\n
# Definition for a binary tree node.\n# class TreeNode(object):\n# def __init__(self, val=0, left=None, right=None):\n# self.val = val\n# self.left = left\n# self.right = right\nclass Solution(object):\n def check(self, root, isBalanced):\n if root is None:\n return 0\n leftDepth = self.check(root.left, isBalanced)\n rightDepth = self.check(root.right, isBalanced)\n if abs(leftDepth - rightDepth) > 1:\n self.isBalanced[0] = False\n return max(leftDepth, rightDepth) + 1\n\n def isBalanced(self, root):\n \"\"\"\n :type root: TreeNode\n :rtype: bool\n \"\"\"\n self.isBalanced = [True]\n self.check(root, self.isBalanced)\n return self.isBalanced[0]<\/pre>\n\n\n\n
Complexity Analysis:<\/strong><\/p>\n\n\n\n
- Height of current node = max(height of left subtree, height of right subtree) + 1.<\/li><\/ul>\n\n\n\n
- Q.2: What is the time complexity of the depth function in the naive approach?<\/a><\/li><\/ul><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n
- Java Code<\/a><\/li>
- Java Code<\/a><\/li>
- Approach 1: Naive<\/a><\/li>
- Sample Test Cases :<\/strong><\/a><\/li><\/ul>
![\"Input](\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/input-1-1024x727.png\")
<\/figure>\n\n\n\n![\"input](\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/input-2-1024x889.png\")
<\/figure>\n\n\n\n