Balanced Binary Tree Leetcode Solution

In this post, we are going to solve the Balanced Binary Tree Leetcode Solution problem of Leetcode. This Leetcode problem is done in many programming languages like C++, Java, and Python.

Balanced Binary Tree Leetcode Solution
Balanced Binary Tree Leetcode Solution

Problem

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as:

a binary tree in which the left and right subtrees of every node differ in height by no more than 1.

Example 1:Balanced Binary Tree Leetcode Solution

Input: root = [3,9,20,null,null,15,7]
Output: true

Example 2:Balanced Binary Tree Leetcode Solution

Input: root = [1,2,2,3,3,null,null,4,4]
Output: false

Example 3:

Input: root = []
Output: true

Constraints:

  • The number of nodes in the tree is in the range [0, 5000].
  • -104 <= Node.val <= 104

Now, lets see the leetcode solution of Balanced Binary Tree Leetcode Solution.

Balanced Binary Tree Leetcode Solution in Python

class Solution:
  def isBalanced(self, root: Optional[TreeNode]) -> bool:
    if not root:
      return True

    def maxDepth(root: Optional[TreeNode]) -> int:
      if not root:
        return 0
      return 1 + max(maxDepth(root.left), maxDepth(root.right))

    return abs(maxDepth(root.left) - maxDepth(root.right)) <= 1 and \
        self.isBalanced(root.left) and self.isBalanced(root.right)

Balanced Binary Tree Leetcode Solution in CPP

class Solution {
 public:
  bool isBalanced(TreeNode* root) {
    if (root == nullptr)
      return true;
    return abs(maxDepth(root->left) - maxDepth(root->right)) <= 1 &&
           isBalanced(root->left) && isBalanced(root->right);
  }

 private:
  int maxDepth(TreeNode* root) {
    if (root == nullptr)
      return 0;
    return 1 + max(maxDepth(root->left), maxDepth(root->right));
  }
};

Balanced Binary Tree Leetcode Solution in Java

class Solution {
  public boolean isBalanced(TreeNode root) {
    if (root == null)
      return true;
    return Math.abs(maxDepth(root.left) - maxDepth(root.right)) <= 1 &&
           isBalanced(root.left) &&
           isBalanced(root.right);
  }

  private int maxDepth(TreeNode root) {
    if (root == null)
      return 0;
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
  }
}

Note: This problem Balanced Binary Tree is generated by Leetcode but the solution is provided by Chase2learn This tutorial is only for Educational and Learning purposes.

Sharing Is Caring