Height, balance check, and mirror of a tree
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
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).