Even-Keeled Tree
EasyTrees
Problem
A tree is even-keeled when, at every node, the heights of its left and right subtrees differ by at most 1 (height counted in nodes; an empty subtree has height 0).
Given the root of a binary tree, return true if it is even-keeled.
Example 1
- Input:
- root = [3, 9, 20, null, null, 15, 7]
- Output:
- true
Example 2
- Input:
- root = [1, 2, 2, 3, 3, null, null, 4, 4]
- Output:
- false
At the root, the left subtree has height 3 and the right subtree height 1.
Constraints
- 0 ≤ number of nodes ≤ 5000
- Tree height ≤ 500
- -10^4 ≤ node.val ≤ 10^4
Hint
Show the first hint
The naive approach recomputes heights from scratch at every node. Can one traversal deliver both facts at once?
Walkthrough
How to approach it
01Clarify before coding
- Must the condition hold at every node or only at the root? At every node: [1, 2, 3, 4, null, null, 5, 6, null, null, 7] has equal heights at the root but fails below.
- Height in nodes or edges? Nodes, but only differences matter, so either works.
- Is the empty tree even-keeled? Yes.
02Brute force
For every node, call a height function on both children and compare.
Cost: O(n log n) on balanced trees but O(n²) on a chain, because each height call re-walks the whole subtree.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.