Tree Height Calculation

Binary TreeDepth-First SearchRecursionTree

Given the root of a binary tree, write a function to compute the height of the tree. The height of a binary tree is the number of edges on the longest downward path between the root and a leaf node.

Example 1

Input

[
  1,
  null,
  2,
  3
]

Output

Explanation. The binary tree looks like this: 1, null, 2. The longest path is from the root (node 1) to node 3 via node 2.

Example 2

Input

[
  1,
  2,
  3,
  4,
  5
]

Output

Explanation. The binary tree looks like this: 1 / \ 2 3 / \ 4 5. Both left and right branches have a length of 1, but the root is also counted as a node, thus the height is 2.

Example 3

Input

[
  1
]

Output

Explanation. The binary tree consists of a single node, thus no edges mean the height is 0.

Follow-up: How would you modify your solution if the tree could contain certain types of cyclic structures?

Constraints:

The input tree will contain at least one node (the root) and at most 1000 nodes. The tree does not contain cycles.

Views: 3