Loading problems...
TL;DR: The optimal solution utilizes a bottom-up Depth-First Search (DFS) to calculate the height of each subtree while simultaneously validating the balance constraint, returning a sentinel value (e.g., -1) immediately upon detecting an imbalance.
In the LeetCode 110 problem, we are asked to determine if a binary tree is height-balanced. A binary tree is considered height-balanced if, for every node in the tree, the height difference between its left and right subtrees is no more than 1. This definition applies recursively; not only must the root satisfy this condition, but every single node within the tree must also satisfy it.
This is a classic interview question that tests your ability to optimize tree traversals. While a naive solution is intuitive, the optimal Balanced Binary Tree solution requires understanding how to propagate information up from the leaves to the root efficiently.
The most straightforward way to solve this problem is to translate the definition directly into code using a top-down approach. For every node, we calculate the height of its left child and the height of its right child, check the difference, and then recursively repeat the process for the children.
getHeight(node) that traverses down to the leaves to calculate the height of a specific node.isBalanced(node) function:
leftHeight = getHeight(node.left).rightHeight = getHeight(node.right).abs(leftHeight - rightHeight) > 1, return false.isBalanced(node.left) && isBalanced(node.right).textfunction getHeight(node): if node is null: return 0 return max(getHeight(node.left), getHeight(node.right)) + 1 function isBalanced(node): if node is null: return true if abs(getHeight(node.left) - getHeight(node.right)) > 1: return false return isBalanced(node.left) AND isBalanced(node.right)
The time complexity of this approach is in the worst case (a skewed tree). This occurs because getHeight is called repeatedly for the same nodes. For a node at depth , getHeight visits it times (once for each ancestor's check). While this might pass the constraint of 5000 nodes, it is computationally redundant and demonstrates a lack of understanding regarding efficient tree traversals.
The key intuition to optimizing the LeetCode 110 solution is to eliminate redundant height calculations. Instead of calculating height from the top down, we can compute it from the bottom up.
In a Postorder Traversal (Left, Right, Root), we visit a node only after visiting its children. This allows us to pass the height of the children up to the parent. However, we need to convey two pieces of information:
We can combine these into a single integer return value. If a subtree is balanced, we return its actual height (a non-negative integer). If a subtree is unbalanced, we return a sentinel error code (e.g., -1).
Visual Description:
Imagine the recursion tree expanding until it hits the null leaves. These leaves return a height of 0 to their parents. As the recursion unwinds (moves back up the stack), each parent node receives the heights of its left and right children. The parent immediately compares these two values. If the difference is greater than 1, or if either child reported an error (-1), the parent stops processing and passes -1 further up the chain. This effectively "short-circuits" the logic for that path, propagating the failure signal to the root.

We implement a helper function (often named dfs or checkHeight) that performs the postorder traversal.
null, its height is 0. This is a balanced state.-1 (indicating it is unbalanced), immediately return -1 to propagate the error.-1, immediately return -1.1, the current subtree is unbalanced. Return -1.max(left_height, right_height) + 1.-1. If it does, the tree is not balanced. Otherwise, it is.Let's trace the algorithm on root = [1, 2, 3, 4, 5, null, null] (where 4 and 5 are children of 2).
dfs(1).dfs(2).dfs(4).
dfs(4.left) (null) returns 0.dfs(4.right) (null) returns 0.abs(0-0) <= 1. Returns max(0,0) + 1 = 1.dfs(5).
dfs(5.left) (null) returns 0.dfs(5.right) (null) returns 0.abs(0-0) <= 1. Returns max(0,0) + 1 = 1.left = 1 (from Node 4), right = 1 (from Node 5).abs(1-1) <= 1. Returns max(1,1) + 1 = 2.dfs(3).
left = 2 (from Node 2), right = 1 (from Node 3).abs(2-1) <= 1. This is true.max(2,1) + 1 = 3.The correctness relies on the inductive property of the postorder traversal.
-1 is returned. Since -1 propagates strictly upwards, the root will eventually receive -1 if any violation exists in the entire tree structure.cpp/** * 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) { return checkHeight(root) != -1; } private: // Returns height of subtree if balanced, or -1 if unbalanced int checkHeight(TreeNode* node) { if (node == nullptr) { return 0; } int leftHeight = checkHeight(node->left); if (leftHeight == -1) return -1; // Propagate failure int rightHeight = checkHeight(node->right); if (rightHeight == -1) return -1; // Propagate failure if (abs(leftHeight - rightHeight) > 1) { return -1; // Current node is unbalanced } return max(leftHeight, rightHeight) + 1; } };
java/** * 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 dfsHeight(root) != -1; } // Returns the height of the tree if balanced, otherwise -1 private int dfsHeight(TreeNode node) { if (node == null) { return 0; } int leftHeight = dfsHeight(node.left); if (leftHeight == -1) return -1; // Left subtree is unbalanced int rightHeight = dfsHeight(node.right); if (rightHeight == -1) return -1; // Right subtree is unbalanced if (Math.abs(leftHeight - rightHeight) > 1) { return -1; // Current node is unbalanced } return Math.max(leftHeight, rightHeight) + 1; } }
python# 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: return self._check_height(root) != -1 def _check_height(self, node: Optional[TreeNode]) -> int: if not node: return 0 left_height = self._check_height(node.left) if left_height == -1: return -1 right_height = self._check_height(node.right) if right_height == -1: return -1 if abs(left_height - right_height) > 1: return -1 return max(left_height, right_height) + 1
Time Complexity: We visit every node in the tree exactly once. At each node, we perform constant-time operations (comparisons and addition). Thus, the time complexity is linear with respect to the number of nodes .
Space Complexity: The space complexity is determined by the recursion stack depth, which corresponds to the height of the tree .
The Tree DFS - Recursive Postorder Traversal pattern is highly reusable. Understanding how to bubble up values from leaves to root is critical for these related problems:
height calculation part of the Balanced Binary Tree solution without the balance check.Q: Why does the naive solution result in Time Limit Exceeded (TLE) or poor performance?
height() is called recursively for every node.Q: Can I just check the balance of the root's left and right children?
abs(height(root.left) - height(root.right)) <= 1 only at the root.true for invalid trees (Incorrectness).Q: Why do we return -1? Can we use a boolean?
true/false from the recursive function while also needing to track height.-1 as a sentinel value.