Problem Statement
How do you find the height of a binary tree? Explain the algorithm and its complexity.
Explanation
The height of a binary tree is the number of edges in the longest path from the root to a leaf node. An empty tree has height negative 1, a tree with only root has height 0, and so on. Finding the height is a fundamental tree operation.
The recursive algorithm is based on the observation that the height of a tree equals one plus the maximum height of its subtrees. For any node, we recursively calculate the height of the left subtree and the height of the right subtree, then return one plus the maximum of these two heights. The base case is when we reach a null node, which has height negative 1.
The algorithm works as follows. If the node is null, return negative 1. Recursively find the height of the left subtree. Recursively find the height of the right subtree. Return one plus the maximum of the left and right heights. This one accounts for the edge from the current node to its child.
Time complexity is O of n where n is the number of nodes, because we visit each node exactly once. Space complexity is O of h where h is the height of the tree, due to the recursion call stack. In the worst case of a skewed tree, this becomes O of n. For a balanced tree, space complexity is O of log n.
The iterative approach uses level-order traversal with a queue. We process the tree level by level, incrementing a counter for each level. Initialize height to 0 and use a queue containing the root. While the queue is not empty, get the number of nodes at current level, process all nodes at this level by dequeuing and enqueuing their children, and increment height after processing each level. This approach has O of n time and O of w space where w is the maximum width of the tree.
Variations of this problem include finding the diameter of a tree which is the longest path between any two nodes, checking if a tree is balanced where heights of subtrees differ by at most 1, and finding the minimum depth which is the shortest path from root to a leaf.
