Balanced Binary Tree - Practice Coding Problems

Balanced Binary Tree - Problem

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

A height-balanced binary tree is defined as: a binary tree in which the left and right subtrees of every node differ in height by no more than 1.

The height of a tree is the number of edges in the longest path from the root to a leaf node. An empty tree has height -1.

Input & Output

Example 1 — Balanced Tree

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

› Output: true

💡 Note: Height of left subtree (9) is 0, height of right subtree (20) is 1. Difference is 1 ≤ 1, so balanced. All other nodes are also balanced.

Example 2 — Unbalanced Tree

$ Input: root = [1,2,2,3,3,null,null,4,4]

› Output: false

💡 Note: The left subtree has height 3 while right subtree has height 0. Difference is 3 > 1, making it unbalanced.

Example 3 — Empty Tree

$ Input: root = []

› Output: true

💡 Note: An empty tree is considered balanced by definition.

Constraints

The number of nodes in the tree is in the range [0, 5000]
-10⁴ ≤ Node.val ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Binary tree with nodes and structure

Height Check

Calculate heights and compare differences

Balance Result

Return true if all nodes satisfy balance condition

Key Takeaway

🎯 Key Insight: Check height difference at every node - if any exceeds 1, the tree is unbalanced

Asked in

a Amazon 15 G Google 12 M Microsoft 8 f Facebook 6

The key insight is to combine height calculation with balance checking in a single DFS traversal. The brute force approach recalculates heights multiple times (O(n²)), while the optimized approach visits each node once and returns early on imbalance. Best approach: Single Pass DFS - Time: O(n), Space: O(h)

Common Approaches

Approach	Time	Space	Notes
✓ Optimized DFS - Single Pass	O(n)	O(h)	Calculate height and check balance in one traversal
Brute Force - Check Height at Every Node	O(n²)	O(h)	Calculate height of left and right subtrees for every node separately

Optimized DFS - Single Pass — Algorithm Steps

Traverse tree in post-order (bottom-up)
For each node, get heights from left and right children
If either child is unbalanced or height difference > 1, return -1
Otherwise return 1 + max(left_height, right_height)

Visualization

Tap to expand

Step-by-Step Walkthrough

Post-order DFS

Visit children first, then process current node

Check Balance

Return -2 if unbalanced, height if balanced

Early Exit

Stop immediately on first imbalance found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

struct TreeNode* createNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

int dfs(struct TreeNode* node) {
    if (!node) return -1;
    
    int leftHeight = dfs(node->left);
    if (leftHeight == -2) return -2;
    
    int rightHeight = dfs(node->right);
    if (rightHeight == -2) return -2;
    
    int diff = leftHeight - rightHeight;
    if (diff < 0) diff = -diff;
    
    if (diff > 1) return -2; // Unbalanced
    
    return 1 + (leftHeight > rightHeight ? leftHeight : rightHeight);
}

bool solution(struct TreeNode* root) {
    return dfs(root) != -2;
}

struct TreeNode* buildTree(char* input) {
    if (strstr(input, "[]") || strstr(input, "[null]")) {
        return NULL;
    }
    
    // Simple parser for basic test cases
    char* token = strtok(input, "[,]");
    if (!token) return NULL;
    
    struct TreeNode* root = createNode(atoi(token));
    struct TreeNode* queue[1000];
    int front = 0, rear = 0;
    queue[rear++] = root;
    
    while (front < rear && (token = strtok(NULL, ",]"))) {
        struct TreeNode* node = queue[front++];
        
        // Remove leading spaces
        while (*token == ' ') token++;
        
        if (strcmp(token, "null") != 0) {
            node->left = createNode(atoi(token));
            queue[rear++] = node->left;
        }
        
        if ((token = strtok(NULL, ",]")) && strcmp(token, "null") != 0) {
            while (*token == ' ') token++;
            node->right = createNode(atoi(token));
            queue[rear++] = node->right;
        }
    }
    
    return root;
}

int main() {
    char input[10000];
    fgets(input, sizeof(input), stdin);
    input[strcspn(input, "\n")] = 0;
    
    struct TreeNode* root = buildTree(input);
    bool result = solution(root);
    printf(result ? "true\n" : "false\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Visit each node exactly once in single DFS traversal

✓ Linear Growth

Space Complexity

O(h)

Recursion call stack depth equals tree height h

✓ Linear Space

832.0K Views

Medium Frequency

~15 min Avg. Time

7.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized DFS - Single Pass — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler