A gardener calls a tree evenly grown when, at every single node, the node's left subtree and right subtree differ in height by at most one. The height of a subtree is the number of nodes on its longest downward path, so an empty subtree has height 0 and a leaf has height 1.
TreeNode(val, left=None, right=None) is in the starter. Keep it.
Write is_evenly_grown(root) -> bool. An empty tree (None) is evenly grown.
# 6 6
# / \ / \
# 2 9 2 9
# / \ /
# 1 4 1
# /
# 0
is_evenly_grown(left_tree) # True
is_evenly_grown(right_tree) # False: at node 6 the left side has height 3, the right side 1
is_evenly_grown(None) # True
- Up to 150,000 nodes and up to 1,000 levels deep; values are arbitrary integers. The Python tests stay within 500 levels, so plain recursion is safe under its default limit of 1,000 frames.
- The check has to hold at every node, not only at the root.
- Aim for O(n): look at each node a constant number of times. Asking for a fresh height at every node can take far longer on tall trees.
Show hint
Let one walk hand back two things from each subtree at once: its height, and whether it's already known to be uneven.