minTreeDepth
that takes in the root node of a Binary Tree and returns the minimum depth of the tree. The minimum depth is defined as the least number of node traversals needed to reach a leaf from the root node. Your method should run in linear O(n) time and use at max O(n) space.Example:
1
/ \
2 3
/ \
4 5
Output : 2
1 -> 3 is the minimum depth, with a 2 node traversal.
null
left and right children. This then becomes a class BFS
problem. When dealing with a tree BFS problem, you should immediately think of Level Order Traversal
. Two Queue
s can be used to traverse a tree in Level Order. The first Queue holds the TreeNode
s of the current level, and the second Queue
holds those of the next level. When skipping to the next level, simply set the next level Queue
to the current level Queue
and create a new Queue
for the next Level.
depth
to 1.Queue curLevel = new LinkedList<>();
Queue nextLevel = new LinkedList<>();
root
to curLevel
. Setup a while
loop that loops until curLevel
becomes empty. Within the while
loop, if you encounter a node with null
left and right nodes, return the depth
up til that point. .poll()
a TreeNode
from curLevel
. If its left and right nodes are not null
, add them to nextLevel
. Check once again if curLevel
is empty. If it is, we need to move over to the next level. Set curLevel
to nextLevel
and create a new LinkedList<>()
for nextLevel
, while incrementing depth
by 1.
public int minTreeDepth(TreeNode root) { }
C
Java
Python