Balanced Binary Tree

Easy

#0110Time: O(N^2) in the worst case (a skewed tree). For each of the N nodes, we might traverse its entire subtree to calculate the height. For a balanced tree, the complexity is closer to O(N log N).Space: O(N) in the worst case (a skewed tree) and O(log N) in the best case (a balanced tree), due to the recursion stack depth.6 companies

Algorithms

Depth-First Search

Data structures

Tree Binary Tree

Companies

Adobe Apple Capgemini Meta

Prompt

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

Example 1:

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

Example 2:

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].
-10⁴ <= Node.val <= 10⁴

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly translates the definition of a balanced binary tree into a recursive algorithm. For each node, it first calculates the heights of its left and right subtrees and checks if the difference is at most one. If this condition holds, it then recursively proceeds to check if the left and right subtrees are themselves balanced. This method is straightforward to understand but is inefficient because it repeatedly calculates the height of the same subtrees.

Algorithm

Define a helper function height(node) that recursively computes the height of a subtree. The height of a null node is 0, and the height of a non-null node is 1 + max(height(node.left), height(node.right)).
Define the main function isBalanced(root).
If the root is null, the tree is balanced, so return true.
Calculate the height of the left subtree, leftHeight = height(root.left).
Calculate the height of the right subtree, rightHeight = height(root.right).
Check if the current node is balanced: if (Math.abs(leftHeight - rightHeight) > 1), return false.
If the current node is balanced, recursively check if its subtrees are also balanced: return isBalanced(root.left) && isBalanced(root.right).

Walkthrough

The core idea is to separate the problem into two distinct recursive functions: one to check for balance (isBalanced) and another to calculate height (height).

height(TreeNode node) function: This helper function computes the height of a subtree rooted at node. It's a standard recursive height calculation. If the node is null, its height is 0. Otherwise, its height is 1 plus the maximum height of its left and right children.
isBalanced(TreeNode root) function: This is the main function. For any given node, it performs three checks: a. It computes the heights of the left and right subtrees using the height helper. b. It checks if the absolute difference between these heights is greater than 1. If it is, the tree is not balanced, and it returns false. c. If the current node is balanced, it must also ensure that all its descendants are balanced. It does this by recursively calling isBalanced on its left and right children.

The entire tree is considered balanced only if the balance property holds true for every single node in the tree. The major performance issue arises from the fact that isBalanced calls height, and both functions traverse the subtrees. This means nodes are visited multiple times, leading to overlapping subproblems that are re-computed.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    // Helper function to calculate the height of a tree.18    private int height(TreeNode node) {19        if (node == null) {20            return 0; // Height of an empty tree is 0.21        }22        // Height is 1 + max height of left/right subtrees.23        return 1 + Math.max(height(node.left), height(node.right));24    }25 26    public boolean isBalanced(TreeNode root) {27        // An empty tree is balanced.28        if (root == null) {29            return true;30        }31 32        // Get heights of left and right subtrees.33        int leftHeight = height(root.left);34        int rightHeight = height(root.right);35 36        // Check if the current node is balanced AND37        // if the left and right subtrees are also balanced.38        if (Math.abs(leftHeight - rightHeight) <= 139                && isBalanced(root.left)40                && isBalanced(root.right)) {41            return true;42        }43 44        return false;45    }46}

Complexity

Time

O(N^2) in the worst case (a skewed tree). For each of the N nodes, we might traverse its entire subtree to calculate the height. For a balanced tree, the complexity is closer to O(N log N).

Space

O(N) in the worst case (a skewed tree) and O(log N) in the best case (a balanced tree), due to the recursion stack depth.

Trade-offs

Pros

Intuitive and easy to understand as it directly models the problem statement.
Clearly separates the logic for height calculation and balance checking.

Cons

Highly inefficient due to redundant computations. The height of a single node might be calculated multiple times as the recursion progresses down the tree.
The time complexity is poor, especially for skewed trees, which can lead to a 'Time Limit Exceeded' error on platforms like LeetCode.

This optimized approach combines the height calculation and balance check into a single recursive pass. It works in a bottom-up manner (similar to a post-order traversal). A helper function is designed to return the height of a subtree only if it's balanced. If an imbalance is detected at any node, it returns a special sentinel value (like -1). This sentinel value is then propagated up the recursion stack, allowing for an early exit and avoiding unnecessary computations. This reduces the time complexity from quadratic to linear.

Algorithm

Define a helper function, checkHeight(node), that returns the height of the subtree if it's balanced, or a sentinel value (e.g., -1) if it's not.
Base Case: If node is null, it's a balanced subtree of height 0. Return 0.
Recursive Step:
- Recursively call leftHeight = checkHeight(node.left). If leftHeight is -1, an imbalance was found below. Propagate the error by immediately returning -1.
- Recursively call rightHeight = checkHeight(node.right). If rightHeight is -1, return -1.
- Check the balance condition at the current node: if (Math.abs(leftHeight - rightHeight) > 1), the current subtree is unbalanced, so return -1.
- If all checks pass, the current subtree is balanced. Return its height: 1 + Math.max(leftHeight, rightHeight).
The main isBalanced(root) function calls checkHeight(root) and returns true if the result is not -1, and false otherwise.

Walkthrough

This approach improves upon the brute-force method by eliminating redundant calculations. Instead of separating height calculation and balance checking, we merge them into a single recursive function that performs a post-order traversal of the tree.

The helper function, let's call it checkHeight, is designed to return two kinds of information:

The height of the subtree: If the subtree rooted at the current node is balanced.
An error code (-1): If the subtree is unbalanced.

This function works as follows:

It recursively calls itself for the left and right children.
When the recursive calls return, it first checks if either of them returned -1. If so, it means an imbalance has already been detected in a lower part of the tree. In this case, there's no need to check the current node; we simply propagate the -1 up the call stack.
If both subtrees are balanced (i.e., their heights are non-negative), we then check the balance condition at the current node: Math.abs(leftHeight - rightHeight) > 1. If this condition is met, the current node is the source of an imbalance, so we return -1.
If the current node is also balanced, we calculate its height as 1 + Math.max(leftHeight, rightHeight) and return it to the parent caller.

The main isBalanced function simply initiates the process by calling checkHeight(root) and checking if the final result is -1. This ensures that every node is visited only once, making the algorithm very efficient.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    // Helper function returns the height of a subtree if it's balanced,18    // otherwise returns -1.19    private int checkHeight(TreeNode node) {20        // Base case: An empty tree is balanced and has a height of 0.21        if (node == null) {22            return 0;23        }24 25        // Recursively check the left subtree.26        int leftHeight = checkHeight(node.left);27        // If the left subtree is unbalanced, propagate the imbalance signal up.28        if (leftHeight == -1) {29            return -1;30        }31 32        // Recursively check the right subtree.33        int rightHeight = checkHeight(node.right);34        // If the right subtree is unbalanced, propagate the imbalance signal up.35        if (rightHeight == -1) {36            return -1;37        }38 39        // Check if the current node is balanced.40        if (Math.abs(leftHeight - rightHeight) > 1) {41            return -1; // Signal imbalance.42        }43 44        // If balanced, return the height of the current node's subtree.45        return 1 + Math.max(leftHeight, rightHeight);46    }47 48    public boolean isBalanced(TreeNode root) {49        // A tree is balanced if its checkHeight is not -1.50        return checkHeight(root) != -1;51    }52}

Complexity

Time

O(N), where N is the number of nodes in the tree, because we visit each node exactly once.

Space

O(H), where H is the height of the tree. This space is used by the recursion stack. In the worst case of a skewed tree, H = N, so the complexity is O(N). For a balanced tree, it's O(log N).

Trade-offs

Pros

Optimal time complexity of O(N) as each node is visited only once.
Efficiently combines height calculation and balance checking into a single pass.
Allows for early termination. As soon as an imbalance is found, it stops processing that branch and returns.

Cons

The logic can be slightly less direct to grasp compared to the brute-force approach because the return value is overloaded (it represents either a valid height or an error code).

Solutions

Solution

1/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public boolean isBalanced ( TreeNode root ) { return height ( root ) >= 0 ; } private int height ( TreeNode root ) { if ( root == null ) { return 0 ; } int l = height ( root . left ); int r = height ( root . right ); if ( l == - 1 || r == - 1 || Math . abs ( l - r ) > 1 ) { return - 1 ; } return 1 + Math . max ( l , r ); } }

1/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root * @return {boolean} */ var isBalanced =2  function (root) {3    const height = (root) => {4      if (!root) {5        return 0;6      }7      const l = height(root.left);8      const r = height(root.right);9      if (l == -1 || r == -1 || Math.abs(l - r) > 1) {10        return -1;11      }12      return 1 + Math.max(l, r);13    };14    return height(root) >= 0;15  };

1/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: bool isBalanced ( TreeNode * root ) { function < int ( TreeNode * ) > height = [ & ]( TreeNode * root ) { if ( ! root ) { return 0 ; } int l = height ( root -> left ); int r = height ( root -> right ); if ( l == - 1 || r == - 1 || abs ( l - r ) > 1 ) { return - 1 ; } return 1 + max ( l , r ); }; return height ( root ) >= 0 ; } };

1# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution : def isBalanced ( self , root : Optional [ TreeNode ]) -> bool : def height ( root ): if root is None : return 0 l , r = height ( root . left ), height ( root . right ) if l == - 1 or r == - 1 or abs ( l - r ) > 1 : return - 1 return 1 + max ( l , r ) return height ( root ) >= 0

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem