Prerequisites: Binary trees, binary tree traversal.
Problem: Given a binary tree, print its minimum depth. The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
Solution Approach:
Basically we need node count from root to lowest hanging leaf. How to get that?
Just traverse down the tree in a similar to postorder manner and whenever we encounter a leaf return 1. While coming up at the root from left and right subtrees, take 1 + the minimum depth found from both the left and right subtrees. That’s it.
Time complexity: O(N), as we need to visit each node at most twice.
Space complexity: O(1), as no extra containers/variables are required.