Find Height - Binary Tree
We can find the height of a binary tree (i.e. the largest number of edges in a path from the root node to a leaf node) by finding the height of the left subtree, the height of the right subtree, then determining the maximum of the two heights, and adding one. Here's a possible implementation:
int height(Node *root) {
if (root == nullptr) return -1;
int lh = height(root->left);
int rh = height(root->right);
return lh > rh ? lh + 1 : rh + 1;
}
Time complexity
The time complexity is O(n) (where n is the number of nodes in the tree) because that's the total work done when we combine the work done by each recursive call. See the video for more detail.
Space complexity
The space complexity is O(h) (where h is the height of the tree) because of the space taken by the call stack. See the video for more detail.