Tree Height

Tree Height

The height of a tree is the number of nodes on the longest path from root to a leaf.

        4         ← height 3
       / \
      2   6       ← height 2
     / \ / \
    1  3 5  7    ← height 1 (leaves)

Height of an empty tree is 0. Height of a single node is 1.

Implementation

At each node, compute the height of both subtrees and take the larger one:

int height(struct Node *root) {
    if (root == NULL) return 0;
    int lh = height(root->left);
    int rh = height(root->right);
    return 1 + (lh > rh ? lh : rh);
}

The ternary (lh > rh ? lh : rh) gives the maximum of the two heights. Adding 1 counts the current node.

Example

For the 7-node tree: height(4) = 1 + max(height(2), height(6)).

• height(2) = 1 + max(height(1), height(3)) = 1 + max(1, 1) = 2
• height(6) = 1 + max(height(5), height(7)) = 1 + max(1, 1) = 2

So height(4) = 1 + max(2, 2) = 3.

Your Task

Implement int height(struct Node *root) that returns the height of the tree.