A small company's org chart is a binary tree: each person has at most two direct reports. Write a function that returns how many levels the chart has, counting the root's level as 1. An empty chart has 0 levels.
A TreeNode class with val, left and right is provided. Trees are written as level-order arrays, with None (null in JavaScript) for a missing person.
text
1count_levels([1, 2, 3, None, 4]) -> 3
2count_levels([1]) -> 1
3count_levels([]) -> 0
Example 1
The deepest person, 4, is on level 3.
In the first example, 1 manages 2 and 3, and 2 manages 4, so there are three levels.
Write count_levels(root) in Python or countLevels(root) in JavaScript. Examples are written in Python: in JavaScript, None is null and True / False are true / false.
Runs privately in your browser. Nothing is sent to a server.Ctrl/⌘ + Enter to run · Esc then Tab to leave the editor
Write your function, then run it against 16 tests.
Breakdown
Stuck? Reveal one step at a time, and try again after each one.
Think about one node
How many levels does the tree under a node have? It's this node's level, plus however many levels its taller side has.
Step 2
Write that as recursion
levels(node) = 1 + max(levels(node.left), levels(node.right)). The children are smaller trees, so the same function answers them.
Step by step1 / 3
A leaf: 1 + max(0, 0) = 1.
Step 3
The base case
An empty tree has 0 levels. That one line also handles leaves: a leaf is 1 + max(0, 0) = 1.
Step 4
Cost
Every node is visited once. The recursion goes as deep as the tree is tall, so it uses O(h) call-stack space. A breadth-first version (counting levels with a queue) avoids deep recursion, which matters for very deep, chain-like trees.
Solution
Give it a real try first: you learn far more from a wrong attempt than from reading the answer.
Return 0 for an empty tree. Otherwise return 1 plus the larger of the left and right subtrees' level counts.