Given a binary tree, find its minimum depth. The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
For example, the minimum depth of the following binary tree is 3. The shortest path is 1 -> 3 -> 6.
The idea is to traverse the binary tree in bottom-up manner using post-order traversal and calculate the minimum depth of left and right subtree for each encountered node. The minimum depth of the subtree rooted at any node is equal to the minimum depth of its left and right subtree plus one. If either left or right subtree does not exist for a node, consider the minimum depth returned by the other subtree.
The algorithm can be implemented as follows in C++, Java, and Python:
C++
|
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
|
#include <iostream>
using namespace std;
// A Binary Tree Node
struct Node
{
int data;
Node *left, *right;
Node(int data)
{
this->data = data;
this->left = this->right = nullptr;
}
};
// Recursive function to find the minimum depth of a path starting
// from the given node in a binary tree
int minDepth(Node *root)
{
// base case
if (root == nullptr) {
return 0;
}
// find minimum depth of the left subtree
int l = minDepth(root->left);
// find minimum depth of the right subtree
int r = minDepth(root->right);
// if left child does not exist, consider depth returned by the right subtree
if (root->left == nullptr) {
return 1 + r;
}
// if right child does not exist, consider depth returned by the left subtree
if (root->right == nullptr) {
return 1 + l;
}
// otherwise choose minimum depth returned by the left and right subtree
return min(l, r) + 1;
}
int main()
{
Node* root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->left->right = new Node(5);
root->right->left = new Node(6);
root->right->right = new Node(7);
root->left->left->right = new Node(8);
root->left->right->right = new Node(9);
root->right->right->left = new Node(10);
root->right->right->left = new Node(11);
root->left->left->right->right = new Node(12);
cout << “The minimum depth is “ << minDepth(root);
return 0;
}
|
Output:
The minimum depth is 3
Java
|
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
|
// A Binary Tree Node
class Node
{
int data;
Node left, right;
Node(int data) {
this.data = data;
this.left = this.right = null;
}
}
class Main {
// Recursive function to find the minimum depth of a path starting
// from the given node in a binary tree
public static int minDepth(Node root)
{
// base case
if (root == null) {
return 0;
}
// find minimum depth of the left subtree
int l = minDepth(root.left);
// find minimum depth of the right subtree
int r = minDepth(root.right);
// if the left child does not exist, consider the depth
// returned by the right subtree
if (root.left == null) {
return 1 + r;
}
// if right child does not exist, consider the depth
// returned by the left subtree
if (root.right == null) {
return 1 + l;
}
// otherwise choose minimum depth returned by the
// left and right subtree
return Integer.min(l, r) + 1;
}
public static void main(String[] args)
{
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.right.right = new Node(7);
root.left.left.right = new Node(8);
root.left.right.right = new Node(9);
root.right.right.left = new Node(10);
root.right.right.left = new Node(11);
root.left.left.right.right = new Node(12);
System.out.println(“The minimum depth is “ + minDepth(root));
}
}
|
Output:
The minimum depth is 3
Python
|
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
# A Binary Tree Node
class Node:
def __init__(self, data, left=None, right=None):
self.data = data
self.left = left
self.right = right
# Recursive function to find the minimum depth of a path starting
# from the given node in binary tree
def minDepth(root):
# base case
if root is None:
return 0
# find minimum depth of the left subtree
l = minDepth(root.left)
# find minimum depth of the right subtree
r = minDepth(root.right)
# if left child does not exist, consider depth returned by the right subtree
if root.left is None:
return 1 + r
# if right child does not exist, consider depth returned by the left subtree
if root.right is None:
return 1 + l
# otherwise choose minimum depth returned by the left and right subtree
return min(l, r) + 1
if __name__ == ‘__main__’:
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
root.left.left.right = Node(8)
root.left.right.right = Node(9)
root.right.right.left = Node(10)
root.right.right.left = Node(11)
root.left.left.right.right = Node(12)
print(“The minimum depth is”, minDepth(root))
|
Output:
The minimum depth is 3
Download Run Code
Output:
The minimum depth is 3
Download Run Code
Output:
The minimum depth is 3
Download Run Code
Output:
The minimum depth is 3
The time complexity of the above solution is O(n), and the auxiliary space used by the program is O(h) for the call stack, where h is the height of the tree.
The above recursive solution is far from optimal as we might end up traversing the whole tree to find a leaf closest to the root node. The idea is to traverse the tree using BFS instead of DFS. Then, the procedure can be terminated on encountering the first leaf node closest to the root.
The standard algorithm for performing BFS on trees is Level Order Traversal. This is demonstrated below in C++, Java, and Python:
C++
|
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
|
#include <iostream>
#include <queue>
using namespace std;
// A Binary Tree Node
struct Node
{
int data;
Node *left, *right;
Node(int data)
{
this->data = data;
this->left = this->right = nullptr;
}
};
// Queue node for storing a pointer to a tree node and its current depth
struct qNode
{
Node* node;
int depth;
};
// Returns true if the given tree node is a leaf, false otherwise
bool isLeaf(Node* node) {
return node->left == nullptr && node->right == nullptr;
}
// Iterative function to find the minimum depth of a path starting
// from the given node in a binary tree
int minDepth(Node* root)
{
// base case
if (root == nullptr) {
return 0;
}
// create an empty queue and push root of the tree with depth as 1
queue<qNode> q;
q.push({root, 1});
// run till queue is empty
while (!q.empty())
{
// pop front node from the queue
Node* node = q.front().node;
int depth = q.front().depth;
q.pop();
// if the popped node is a leaf node, return its depth
if (isLeaf(node)) {
return depth;
}
// enqueue left child of the popped node with +1 depth
if (node->left) {
q.push({node->left, depth + 1});
}
// enqueue right child of the popped node with +1 depth
if (node->right) {
q.push({node->right, depth + 1});
}
}
}
int main()
{
Node* root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->left->right = new Node(5);
root->right->left = new Node(6);
root->right->right = new Node(7);
root->left->left->right = new Node(8);
root->left->right->right = new Node(9);
root->right->right->left = new Node(10);
root->right->right->left = new Node(11);
root->left->left->right->right = new Node(12);
cout << “The minimum depth is “ << minDepth(root);
return 0;
}
|
Output:
The minimum depth is 3
Java
|
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
|
import java.util.ArrayDeque;
import java.util.Queue;
// A Binary Tree Node
class Node {
int data;
Node left, right;
Node(int data) {
this.data = data;
this.left = this.right = null;
}
}
// Queue node for storing a pointer to a tree node and its current depth
class qNode {
Node node;
int depth;
public qNode(Node node, int depth) {
this.node = node;
this.depth = depth;
}
}
class Main
{
// Returns true if the given tree node is a leaf, false otherwise
public static boolean isLeaf(Node node) {
return node.left == null && node.right == null;
}
// Iterative function to find the minimum depth of a path starting
// from the given node in a binary tree
public static int minDepth(Node root)
{
// base case
if (root == null) {
return 0;
}
// create an empty queue and push root of the tree with depth as 1
Queue<qNode> q = new ArrayDeque<>();
q.add(new qNode(root, 1));
// run till queue is empty
while (!q.isEmpty())
{
// pop front node from the queue
Node node = q.peek().node;
int depth = q.peek().depth;
q.poll();
// if the popped node is a leaf node, return its depth
if (isLeaf(node)) {
return depth;
}
// enqueue left child of the popped node with +1 depth
if (node.left != null) {
q.add(new qNode(node.left, depth + 1));
}
// enqueue right child of the popped node with +1 depth
if (node.right != null) {
q.add(new qNode(node.right, depth + 1));
}
}
return 0;
}
public static void main(String[] args)
{
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.right.right = new Node(7);
root.left.left.right = new Node(8);
root.left.right.right = new Node(9);
root.right.right.left = new Node(10);
root.right.right.left = new Node(11);
root.left.left.right.right = new Node(12);
System.out.println(“The minimum depth is “ + minDepth(root));
}
}
|
Output:
The minimum depth is 3
Python
|
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
|
from collections import deque
# A Binary Tree Node
class Node:
def __init__(self, data, left=None, right=None):
self.data = data
self.left = left
self.right = right
# Queue node for storing a pointer to a tree node and its current depth
class qNode:
def __init__(self, node=None, depth=None):
self.node = node
self.depth = depth
# Returns True if the given tree node is a leaf, False otherwise
def isLeaf(node):
return node.left is None and node.right is None
# Iterative function to find the minimum depth of a path starting
# from the given node in binary tree
def minDepth(root):
# base case
if root is None:
return 0
# create an empty queue and push root of the tree with depth as 1
q = deque()
q.append(qNode(root, 1))
# run till queue is empty
while q:
# pop front node from the queue
front = q.popleft()
node = front.node
depth = front.depth
# if the popped node is a leaf node, return its depth
if isLeaf(node):
return depth
# enqueue left child of the popped node with +1 depth
if node.left:
q.append(qNode(node.left, depth + 1))
# enqueue right child of the popped node with +1 depth
if node.right:
q.append(qNode(node.right, depth + 1))
if __name__ == ‘__main__’:
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
root.left.left.right = Node(8)
root.left.right.right = Node(9)
root.right.right.left = Node(10)
root.right.right.left = Node(11)
root.left.left.right.right = Node(12)
print(“The minimum depth is”, minDepth(root))
|
Output:
The minimum depth is 3
Download Run Code
Output:
The minimum depth is 3
Download Run Code
Output:
The minimum depth is 3
Download Run Code
Output:
The minimum depth is 3
The time complexity of the above solution is O(n), and the extra space used by the program is O(n) for queue data structure.
