Balanced Binary Tree

Easy · Trees · Explanation and code example

Iterative DFS

How it works

The recursive DFS solution computes height and balance in one postorder traversal.
This iterative version does the same thing, but simulates recursion using a stack.

The idea:

  • We must visit each node after its children (postorder).
  • Once both children of a node are processed, we already know their heights.
  • Then we:
    1. Check if the height difference ≤ 1
    2. Save the node's height (1 + max(left, right))

If any node is unbalanced, return false immediately.

Steps

  1. Use a stack to simulate postorder traversal.
  2. Use a dictionary/map (depths) to store the height of each visited node.
  3. For each node:
    • Traverse left until possible.
    • When left is done, try right.
    • When both children are done:
      • Get their heights from depths.
      • If the difference > 1 → tree is unbalanced → return false.
      • Compute current node height and store it.
  4. If the traversal completes without violations → return true.

Complexity

  • Time complexity: O(n)
  • Space complexity: O(n)

Things to watch for

Only Checking the Root Node

A tree is balanced only if every node (not just the root) has subtrees with heights differing by at most 1. Checking only the root misses imbalanced subtrees deeper in the tree.

Returning Height of 0 for Leaf Nodes

A leaf node has height 1, not 0. Returning 0 for leaves causes off-by-one errors in height calculations. The base case should return 0 only for null nodes.

Python code example

# 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):
        stack = []
        node = root
        last = None
        depths = {}

        while stack or node:
            if node:
                stack.append(node)
                node = node.left
            else:
                node = stack[-1]
                if not node.right or last == node.right:
                    stack.pop()
                    left = depths.get(node.left, 0)
                    right = depths.get(node.right, 0)

                    if abs(left - right) > 1:
                        return False

                    depths[node] = 1 + max(left, right)
                    last = node
                    node = None
                else:
                    node = node.right

        return True

C++ code example

/**
 * 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) {
        stack<TreeNode*> stack;
        TreeNode* node = root;
        TreeNode* last = nullptr;
        unordered_map<TreeNode*, int> depths;

        while (!stack.empty() || node != nullptr) {
            if (node != nullptr) {
                stack.push(node);
                node = node->left;
            } else {
                node = stack.top();
                if (node->right == nullptr || last == node->right) {
                    stack.pop();
                    int left = depths[node->left];
                    int right = depths[node->right];
                    if (abs(left - right) > 1) return false;
                    depths[node] = 1 + max(left, right);
                    last = node;
                    node = nullptr;
                } else {
                    node = node->right;
                }
            }
        }
        return true;
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode Watch NeetCode on YouTube

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations