Easy · Sentinel Postorder
Understand → Visualise → Practice.
Return whether every binary-tree node has left and right subtree heights differing by at most one.
Compute heights bottom-up. A height function that returns −1 for an unbalanced subtree lets one postorder pass both measure and check every node.
An empty position (past the array or null) has height 0.
Get the left and right heights; if either is −1 or they differ by more than 1, return −1.
Return 1 + max(left, right); the tree is balanced if the root's result isn't −1.
O(n) time and O(h) recursion space.
Calling a separate height function at every node is O(n²) on a skewed tree.
Read the full guides first: Binary Trees and Traversals, Binary Search Trees, Graphs, BFS and DFS, Weighted Graphs, Dijkstra and Union–Find.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.