Home Minimum Depth of Binary Tree
Post
Cancel

Minimum Depth of Binary Tree

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
This post is licensed under CC BY 4.0 by the author.

Implement Queue using Stacks

Average of Levels in Binary Tree