Calculate the height of a binary tree.
EasyUnlock detailed company stats for this questionUpgrade
Given the root of a binary tree, return its maximum depth: the number of nodes along the longest path from the root down to a leaf.
Trees in the examples and tests are written in level order, with null for a missing child.
Example 1
Input: root = [3, 9, 20, null, null, 15, 7] Output: 3 3 / \ 9 20 / \ 15 7
The longest paths, such as 3 -> 20 -> 15, have three nodes.
Example 2
Input: root = [1, null, 2] Output: 2
Constraints
- The tree has between
0and10^4nodes. -100 <= Node.val <= 100
Approach
The depth of a tree is one more than the depth of its deeper subtree, and that definition is already an algorithm. An empty tree has depth 0. Any other tree has depth 1 + max(depth(left), depth(right)). The recursion reaches every node once, adding one level each time it returns.
Steps
- If
rootis empty, return0. - Compute the depth of the left and right subtrees recursively.
- Return one plus the larger of the two.
Complexity
- Time:
O(n). Each node is visited once. - Space:
O(h), wherehis the height of the tree, for the recursion stack. That'sO(n)for a tree shaped like a chain.
Common mistakes
- Returning
1for an empty tree. An empty tree has depth0, and a single node has depth1. - Counting edges instead of nodes. This problem counts the nodes on the path, so a single node has depth
1, not0.
Interview experiences
1 sharedRelated questions
Calculate the cost of cash?Print the left view of a binary tree.Check if a given binary tree is height balanced.Related courses

Course

Course



