Prerequisites: Binary Trees, Binary Trees Traversal Techniques.
Problem: Given a connected binary tree with N nodes, find the height of it.
(Note: The height of a binary tree is the number of edges between the tree’s root and its furthest leaf.)
Solution Approach:
We know that the height of a binary tree is the number of edges between the tree’s root and its furthest leaf.
Similarly, the depth of a binary tree is the number of nodes between the tree’s root and its furthest leaf.
So basically, height of the tree = max(0, depth of the tree - 1);
We can traverse the tree down in a postorder manner and keep track of depth of the root,
Once we get the depth, return the height using the above equation.
It will become more clear once we take a look at the solution.
Time Complexity: O(N), as we need to traverse each node at least once.
Space Complexity: O(1), as we don’t need any extra space.