LeetCode: Balanced Binary Tree

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 depth of the two subtrees of every node never differ by more than 1.

---

We can check by the definition: left subtree is balanced, right subtree is balanced and the depth of two subtrees never defer by more than 1.

C++ Code:

/*
 * func: get_height
 * goal: get the height of the binary tree
 * @param root: root node of the tree
 * return: the height of the tree
 */
int get_height(TreeNode *root){
    if(root == nullptr){
        return 0;
    }else{
        int left_height = get_height(root->left);
        int right_height = get_height(root->right);
        
        return left_height > right_height ? left_height + 1 : right_height + 1;
    }
}

/*
 * func: is_balanced
 * goal: to check if the tree is height balanced
 * @param root: root node of the tree
 * return: true or false
 */
bool is_balanced(TreeNode *root){
    if(root == nullptr){
        return true;
    }else{
        int left_height = get_height(root->left);
        int right_height = get_height(root->right);
        
        return is_balanced(root->left) && is_balanced(root->right) && (abs(left_height-right_height) <= 1);
    }
}

Python Code:

# func: to get the height of the current node
#       if tree start from current node is not balanced, return -2
#       height starts from -1
# @param: root node of the tree
# @return: height
def get_height(node):
    if not node:
        return -1
    left_height = get_height(node.left)
    if left_height == -2:
        return -2

    right_height = get_height(node.right)
    if right_height == -2:
        return -2

    if abs(left_height-right_height) > 1:
        return -2

    return max(left_height, right_height) + 1

# func: to check if the tree is height balanced
# @param root: root node of the tree
# @return: True or False
def is_balanced(root):
    return get_height(root) != -2