Height, balance check, and mirror of a tree

Easy

Problem

Three basic recursions. Height (maximum depth): the number of nodes on the longest root-to-leaf path. Balanced: at every node, the heights of the two subtrees differ by at most 1. Mirror (invert): swap every node's left and right children.

Example 1

Input:  [3, 9, 20, null, null, 15, 7]
Output: height 3, balanced true

Example 2

Input:  mirror of [4, 2, 7, 1, 3, 6, 9]
Output: [4, 7, 2, 9, 6, 3, 1]

Also asked as: Height of a tree · Check if a tree is balanced or not · Mirror of a tree · Check if 2 trees are mirror or not · Tree Isomorphism Problem

Test cases

Case 1

Input:    [3,9,20,null,null,15,7]
Expected: true

Case 2

Input:    [1,2,2,3,3,null,null,4,4]
Expected: false

Case 3

Input:    []
Expected: true

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution2 approaches

1. One DFS returning height (−1 signals imbalance)

Time O(n)Space O(h)

Height = 1 + max(childHeights). Balanced iff every node’s subtree heights differ by ≤ 1 — propagate −1 upward on the first violation.

function height(n) { return n ? 1 + Math.max(height(n.left), height(n.right)) : 0; }
function isBalanced(root) {
const check = (n) => {
if (!n) return 0;
const l = check(n.left); if (l === -1) return -1;
const r = check(n.right); if (r === -1) return -1;
return Math.abs(l - r) > 1 ? -1 : 1 + Math.max(l, r);
};
return check(root) !== -1;
}

2. Mirror (invert) and "are two trees mirrors?"

Time O(n)Space O(h)

Invert: swap children recursively. Two trees are mirrors iff a.left ≡ mirror of b.right and a.right ≡ mirror of b.left.

function mirror(n) {
if (!n) return null;
[n.left, n.right] = [mirror(n.right), mirror(n.left)];
return n;
}
function areMirror(a, b) {
if (!a && !b) return true;
if (!a || !b || a.val !== b.val) return false;
return areMirror(a.left, b.right) && areMirror(a.right, b.left);
}
// Isomorphic: like areMirror but allow EITHER (same children) OR (swapped children).