To solve the problem, traverse the binary tree using DFS. For each node, calculate the height of its subtrees and ensure the balance condition is met. If the difference between the heights of the left and right subtrees is greater than 1, the tree is unbalanced.
Problem Statement
You are given the root of a binary tree. A binary tree is considered balanced if the left and right subtrees of every node differ in height by at most one. Return true if the tree is balanced, otherwise return false.
For example, for a binary tree with nodes [3,9,20,null,null,15,7], the tree is balanced. However, a tree like [1,2,2,3,3,null,null,4,4] is unbalanced due to a large height difference between subtrees.
Examples
Example 1
Input: root = [3,9,20,null,null,15,7]
Output: true
Example details omitted.
Example 2
Input: root = [1,2,2,3,3,null,null,4,4]
Output: false
Example details omitted.
Example 3
Input: root = []
Output: true
Example details omitted.
Constraints
- The number of nodes in the tree is in the range [0, 5000].
- -104 <= Node.val <= 104
Solution Approach
Tree Traversal with Height Calculation
A Depth-First Search (DFS) traversal can be used to visit every node of the tree. While traversing, we will compute the height of the left and right subtrees for each node. The tree is balanced if the difference between these heights is at most 1. The traversal continues until all nodes are checked or an imbalance is detected early.
State Tracking for Early Termination
While computing heights during DFS, keep track of any imbalance condition (difference of height greater than 1). If an imbalance is detected at any point, we can stop further traversal and immediately return false. This avoids unnecessary work and improves efficiency.
Time and Space Complexity Considerations
The time complexity for this approach depends on the total number of nodes in the tree, as every node needs to be visited. Therefore, the time complexity is O(n), where n is the number of nodes. The space complexity also depends on the depth of the tree, which, in the worst case, is O(n) for a skewed tree, or O(log n) for a balanced tree.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
The time complexity is O(n) due to the DFS traversal, as each node is visited once. The space complexity is O(h), where h is the height of the tree, because of the recursive call stack in DFS. In the worst case, the height could be n (a skewed tree), resulting in O(n) space complexity.
What Interviewers Usually Probe
- Do you understand the difference between balanced and unbalanced trees?
- Can you explain how DFS helps in both height calculation and detecting imbalances?
- Will you handle edge cases like an empty tree or a skewed tree efficiently?
Common Pitfalls or Variants
Common pitfalls
- Not handling edge cases like an empty tree, which should return true.
- Missing the early termination by not checking imbalance during traversal, leading to unnecessary work.
- Incorrectly calculating the height of subtrees, which can cause false results in balance checking.
Follow-up variants
- Check if the tree is a full binary tree.
- Find the diameter of the tree, which is the longest path between any two nodes.
- Determine if a binary tree is perfect, meaning all leaf nodes are at the same level and every parent has two children.
How GhostInterview Helps
- Screenshots of tree structure inputs or outputs for visualizing the problem.
- A step-by-step explanation path with complexity breakdown and how to approach each step.
- Live screen-share assistance or visual walkthrough of DFS traversal and height checking.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What is a height-balanced binary tree?
A height-balanced binary tree is one where, for every node, the height difference between the left and right subtrees is at most one.
How do you calculate the height of a binary tree node?
The height of a node is calculated as 1 plus the maximum height of its left and right subtrees.
What happens if the tree is unbalanced?
If the difference in height between any two subtrees of a node exceeds 1, the tree is considered unbalanced, and the function should return false.
What should you do if an imbalance is found during DFS?
If an imbalance is found during DFS, you should immediately return false without continuing the traversal, as further checks are unnecessary.
How do you handle an empty tree?
An empty tree is considered balanced by definition, so the function should return true for this case.
Need direct help with Balanced Binary Tree instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Balanced Binary Tree from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Find the minimum depth of a binary tree, which is the shortest path from the root node to the nearest leaf node.
Open problem page#112 Path SumDetermine if a binary tree has a root-to-leaf path where the sum of node values equals a given target sum, using DFS or BFS traversal techniques.
Open problem page#113 Path Sum IIFind all root-to-leaf paths in a binary tree where the sum of node values equals a given target using DFS backtracking.
Open problem page