Balanced Binary Tree

1. Problem Description

Given a binary tree, determine whether it is a balanced binary tree.

2. Approach

Get the tree height from Depth of a Binary Tree + require the height difference between the left and right subtrees to be <= 1.

3. Implementation

• java

public class 平衡二叉树
{
    public boolean IsBalanced_Solution(TreeNode root)
    {
        // Check parameters
        if (root == null)
        {
            return true;
        }
        // Get the heights of the left and right subtrees; the difference must be at most 1
        return Math.abs(this.getTreeDepth(root.right) - this.getTreeDepth(root.left)) <= 1 &&
            // Apply the same logic to the left subtree
            this.IsBalanced_Solution(root.left) &&
            // Apply the same logic to the right subtree
            this.IsBalanced_Solution(root.right);
    }

    private int getTreeDepth(TreeNode root)
    {
        if (root == null)
        {
            return 0;
        }

        return 1 + Math.max(this.getTreeDepth(root.left), this.getTreeDepth(root.right));
    }
}

• go

/*
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */

/**
 *
 * @param pRoot TreeNode class
 * @return bool
 */
// Time complexity: O(N²)
// Space complexity: O(N)
func IsBalanced_Solution(pRoot *TreeNode) bool {
	if pRoot == nil {
		return true
	}

	return abs(getHeight(pRoot.Left)-getHeight(pRoot.Right)) < 2 && IsBalanced_Solution(pRoot.Left) && IsBalanced_Solution(pRoot.Right)
}

func getHeight(node *TreeNode) int {
	if node == nil {
		return 0
	}
	return 1 + max(getHeight(node.Left), getHeight(node.Right))
}

func abs(v int) int {
	if v < 0 {
		return -v
	}
	return v
}


func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

4. References

• Balanced Binary Tree - NowCoder
• 110. Balanced Binary Tree - LeetCode