![Cover image for [Day 2][Easy] 111. Minimum Depth of Binary Tree](https://res.cloudinary.com/practicaldev/image/fetch/s--if_k1Qee--/c_imagga_scale,f_auto,fl_progressive,h_420,q_auto,w_1000/https://dev-to-uploads.s3.amazonaws.com/uploads/articles/6oqem0neu5u4aacymnd4.jpg)
Problem Link: https://leetcode.com/problems/minimum-depth-of-binary-tree
Requirement:
Given the binary tree, we have to find its minimum depth. The minimum depth is the path between root and leaf node where there is a minimum number of nodes between them i.e. the number of nodes between root and nearest leaf node.
Solution:
Depth can be calculated by (modifying) the Depth First Search algorithm to account for depth. We will add a parameter depth which will be incremented whenever we go down by a level. If we found a node with no child (i.e. leaf node) then we will check if the depth at that point is minimum or not. This will be done for all leaf nodes (as DFS is a recursive exhaustive algorithm).
# 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:
minDepth = sys.maxsize
def dfs(node: TreeNode, depth: int) -> int:
nonlocal minDepth
if node.left == None and node.right == None: # Leaf Node
minDepth = min(minDepth, depth)
return
if node.left != None: # Go Left
dfs(node.left, depth + 1)
if node.right != None: # Go Right
dfs(node.right, depth + 1)
if root != None:
dfs(root, 1)
return minDepth
return 0
Further optimization:
We are only interested in depth so instead of having a separate parameter for it we can calculate it on the go. We can opt for a greedy recursive algorithm.
class Solution:
def minDepth(self, root: Optional[TreeNode]) -> int:
if root == None:
return 0
L, R = self.minDepth(root.left), self.minDepth(root.right)
return (min(L, R) if L and R else max(L, R)) + 1
Thanks for reading.
Top comments (0)