View Minimum Depth of Binary Tree on LeetCode
Statistics
Time Spent Coding
15 minutes
Time Complexity
O(n) - Each node in the tree must be visited, resulting in the O(n) time complexity.
Space Complexity
O(n) - The number of recursive calls is at most n and will be stored in the memory stack, resulting in the O(n) space complexity.
Memory Beats
54.32% of other sumbissions
Explanation
The algorithm explores all paths and returns the path with the minimum length by checking both children and recursively calling the minDepth method on them.
If the node is none, then return 0.
If a leaf is found, the algorithm terminates the recursive calls and returns 1.
If a leaf is not found, it returns the lowest of the children’s recursive calls.
Algorithm and Data Structure Used
Depth-First Search - An algorithm for traversing a tree data structure. The algorithm begins at the root node and searches until it can not continue any deeper. Once at the deepest point, the algorithm works backward until all the nodes have been visited.
Binary Tree - A rooted tree where every node has at most two children, the left and right children.
Visual Examples
Depth-first search being performed on a tree, click to view
Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def minDepth(self, root: Optional[TreeNode]) -> int:
if root == None: return 0
l = root.left
r = root.right
# Leaf found
if l == None and r == None:
return 1
else:
lowest = float(inf)
if l:
lowest = min(lowest,self.minDepth(l))
if r:
lowest = min(lowest,self.minDepth(r))
return lowest + 1