Question

write a recursive function to compute the height of a tree, defined as the length of the longest path from the root to a leaf node.

Answer 1

The code in Python is:

def tree_height(node):
if node is None:
return 0
else:
left_height = tree_height(node.left)
right_height = tree_height(node.right)
return max(left_height, right_height) + 1

Step-by-step explanation:

To write a recursive function to compute the height of a tree, you can define the base case when the tree is empty, which would have a height of 0.

Then, for each node with children, you recursively calculate the height of its left and right subtrees, and return the maximum of the two heights plus one.

Here's the code in Python:

def tree_height(node):
if node is None:
return 0
else:
left_height = tree_height(node.left)
right_height = tree_height(node.right)
return max(left_height, right_height) + 1

This function will calculate the height of a binary tree by recursively finding the maximum height of its left and right subtrees and adding 1 for the current node.