Let's start with two examples to visualize the tree height for different trees:

To solve this problem, like in all recursive solutions, we'll define a base case and a recursive definition.

Base Case

In this problem, like in many others dealing with binary trees, the base case occurs when the node is null. Since we are trying to find the maximum depth, which is an integer, we need to return an integer when the node is null.

The node that is null doesn't have any height (its height is zero). We can return 0 in this case.

• Base Case: If the node is null, return 0.

Recursive Definition

Remember our recursive definition template from this assignment. We'll have to update it slightly to include the calculation. Here is the modified template.

The [problem description] of the [data structure] is [1] or [value of element], [operation] the [min/max/comparison] between the left and right subtrees of the [data structure].

Let's break down each part enclosed in square brackets:

• [problem description]: Height

• [data structure]: Binary Tree

• [1] or [value of element]: This means in some subproblems we'll be adding the number 1 and sometimes the value of the node.

• [operation]: This can be "+", "-" etc.

• [min/max/comparison]: This means that we are taking either the minimum, maximum, or, for example, comparing the height of the left subtree and the height of the right subtree.

If we fill in the template, we get:

• Recursive Definition: The height of the binary tree is 1 plus the maximum between the height of the left subtree and the height of the right subtree.

Let's explain this further by creating a tree step-by-step:

Step 1: Initially, we have only one node, so the result is one plus the maximum between the height of the left subtree and the height of the right subtree. Since there are no children nodes, the height of the left and right subtrees are both zero.

Step 2: Once we add a node on the right, the result becomes 1 plus the maximum between the height of the left subtree (0) and the height of the right subtree (1), which adds up to 2.

Step 3: When we add another node on the right, the result becomes 1 plus the maximum between the maximum depth of the left subtree (0) and the maximum depth of the right subtree (2), which adds up to 3.

Step 4: If we add another node to the left of node 3, the result remains 3 since the maximum depth of the binary tree with the root 3 hasn't changed and it's still 2. This is the node itself plus the maximum between the maximum depth of its left subtree (1) and the maximum depth of its right subtree (1).

Step 5: Finally, if we add a node to the left of node 1, the result won't change. The maximum depth of the left subtree with node 2 as the root is less than the maximum depth of the right subtree with node 3 as the root.