Check balanced tree

Problem: check if given tree is balanced

Balanced Definition:

1. Height of left and right subtree <= 1

2. Right and left subtree also balanced

Solution: Recursive post order traversal

Base Case: if root == null return true

Recursive rule:

1. If left or right height differ by more than 1, return false

2. check left && right

Implementation:

public boolean balanceCheck(TreeNode root){
    if (root == null) return true;
    
    int leftHeight = getHeight(root.left);
    int rightHeight = getHeight(root.right);
    
    if (Math.abs(leftHeight - rightHeight) > 1) return false;
    
    return balanceCheck(root.left) && balancedCheck(root.right);
}

Time complexity:

Every node visited, each node checks height of left and right

Each level O(N) * Log(N) levels

O(N LogN)

Space Complexity:

No new struct generated

O(1)