Problem Statement

Given a root node of the binary tree, return the depth (or height) of a binary tree.

The Depth of the binary tree refers to the number of nodes along the longest path from the root node to the farthest leaf node. If the tree is empty, the depth is 0.

A note on the counting, because it differs from the chapter. Introduction to Tree measures height and depth in edges, which is the usual definition in textbooks. This question counts nodes, which is the convention the original version of it uses, and the two differ by exactly one for a non-empty tree. A single node has height 0 in edges and depth 1 here. Read the definition given with a question before answering it, since interviewers use both conventions and rarely say which one they mean.

How to read the input. The array is the tree written out level by level, left to right, with null for a missing child, and the trailing children of a null are left out. So [1, 2, 3, 4, 5] is the root 1 with children 2 and 3, and 2 in turn has children 4 and 5. You never have to parse it yourself: the exercise hands your function a root node that has already been built.

Examples

Example 1

• Input: root = [1, 2, 3, 4, 5]

• Expected Output: 3
• Explanation: The longest path is 1->2->4 or 1->2->5 with 3 nodes.

Example 2

• Input: root = [1, null, 2, null, 3]

• Expected Output: 3
• Justification: There's only one path 1->2->3 with 3 nodes.

Example 3

• Input: root = [1, 2, 3, 4, 7, null, null, null, null, null, 9]

• Expected Output: 4
• Justification: The longest path is 1->2->7->9 with 4 nodes.

Constraints:

• The number of nodes in the tree is in the range [0, 10⁴].
• -100 <= Node.val <= 100

Try it yourself

Try solving this question here: