""" 0111.1 - Solution 1 - Recursive DFS """
#####################################################################################
# Imports
#####################################################################################
from typing import Optional
#####################################################################################
# Classes
#####################################################################################
class TreeNode:
"""TreeNode Class"""
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
"""Solution Class"""
def minDepth(self, root: Optional[TreeNode]) -> int:
"""Minimum Depth of Binary Tree Function"""
if not root:
return 0
# If only right child exists, recurse right
if not root.left:
return 1 + self.minDepth(root.right)
# If only left child exists, recurse left
if not root.right:
return 1 + self.minDepth(root.left)
# Both children exist, take the minimum
return 1 + min(self.minDepth(root.left), self.minDepth(root.right))
#####################################################################################
# Functions
#####################################################################################
def testcase():
"""Test Function"""
# Example 1: [3,9,20,null,null,15,7] -> 2
root1 = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
print(Solution().minDepth(root1))
# Example 2: [2,null,3,null,4,null,5,null,6] -> 5
root2 = TreeNode(2, None, TreeNode(3, None, TreeNode(4, None, TreeNode(5, None, TreeNode(6)))))
print(Solution().minDepth(root2))
# Edge case: empty tree -> 0
print(Solution().minDepth(None))
#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
testcase()
""" 0111.2 - Solution 2 - BFS Level-Order Traversal """
#####################################################################################
# Imports
#####################################################################################
from typing import Optional
from collections import deque
#####################################################################################
# Classes
#####################################################################################
class TreeNode:
"""TreeNode Class"""
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
"""Solution Class"""
def minDepth(self, root: Optional[TreeNode]) -> int:
"""Minimum Depth of Binary Tree Function"""
if not root:
return 0
queue = deque([(root, 1)])
while queue:
node, depth = queue.popleft()
# First leaf node found is at minimum depth
if not node.left and not node.right:
return depth
if node.left:
queue.append((node.left, depth + 1))
if node.right:
queue.append((node.right, depth + 1))
return 0
#####################################################################################
# Functions
#####################################################################################
def testcase():
"""Test Function"""
# Example 1: [3,9,20,null,null,15,7] -> 2
root1 = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
print(Solution().minDepth(root1))
# Example 2: [2,null,3,null,4,null,5,null,6] -> 5
root2 = TreeNode(2, None, TreeNode(3, None, TreeNode(4, None, TreeNode(5, None, TreeNode(6)))))
print(Solution().minDepth(root2))
# Edge case: empty tree -> 0
print(Solution().minDepth(None))
#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
testcase()
