Find the minimum depth of a binary tree
Given a binary tree, find its minimum depth. The minimum depth is the total 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 a bottom-up manner using postorder 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 one more than the minimum depth of its left and right subtree. 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 65 66 67 |
#include <iostream> using namespace std; // Data structure to store 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 findMinDepth(Node* root) { // base case if (root == nullptr) { return 0; } // find the minimum depth of the left subtree int l = findMinDepth(root->left); // find the minimum depth of the right subtree int r = findMinDepth(root->right); // if the left child does not exist, consider the depth // returned by the right subtree if (root->left == nullptr) { return 1 + r; } // if the right child does not exist, consider the depth // returned by the left subtree if (root->right == nullptr) { return 1 + l; } // otherwise, choose the 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 " << findMinDepth(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 |
// Data structure to store 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 findMinDepth(Node root) { // base case if (root == null) { return 0; } // find the minimum depth of the left subtree int l = findMinDepth(root.left); // find the minimum depth of the right subtree int r = findMinDepth(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 the right child does not exist, consider the depth // returned by the left subtree if (root.right == null) { return 1 + l; } // otherwise, choose the 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 " + findMinDepth(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 |
# Data structure to store 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 a binary tree def findMinDepth(root): # base case if root is None: return 0 # find the minimum depth of the left subtree l = findMinDepth(root.left) # find the minimum depth of the right subtree r = findMinDepth(root.right) # if the left child does not exist, consider the depth # returned by the right subtree if root.left is None: return 1 + r # if the right child does not exist, consider the depth # returned by the left subtree if root.right is None: return 1 + l # otherwise, choose the 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', findMinDepth(root)) |
Output:
The minimum depth is 3
The time complexity of the above solution is O(n), where n is the total number of nodes in the binary tree. The auxiliary space required 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 upon 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; // Data structure to store 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 QueueNode { 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 findMinDepth(Node* root) { // base case if (root == nullptr) { return 0; } // create an empty queue and push the root node with a depth of 1 queue<QueueNode> q; q.push({root, 1}); // run till queue is empty while (!q.empty()) { // dequeue front node 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 " << findMinDepth(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 91 92 93 94 |
import java.util.ArrayDeque; import java.util.Queue; // Data structure to store 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 QueueNode { Node node; int depth; public QueueNode(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 findMinDepth(Node root) { // base case if (root == null) { return 0; } // create an empty queue and push the root node with a depth of 1 Queue<QueueNode> q = new ArrayDeque<>(); q.add(new QueueNode(root, 1)); // run till queue is empty while (!q.isEmpty()) { // dequeue front node 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 QueueNode(node.left, depth + 1)); } // enqueue right child of the popped node with +1 depth if (node.right != null) { q.add(new QueueNode(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 " + findMinDepth(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 73 |
from collections import deque # Data structure to store 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 QueueNode: 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 a binary tree def findMinDepth(root): # base case if root is None: return 0 # create an empty queue and push the root node with a depth of 1 q = deque() q.append(QueueNode(root, 1)) # run till queue is empty while q: # dequeue front node 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(QueueNode(node.left, depth + 1)) # enqueue right child of the popped node with +1 depth if node.right: q.append(QueueNode(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', findMinDepth(root)) |
Output:
The minimum depth is 3
The time complexity of the above solution is O(n), where n is the total number of nodes in the binary tree. The extra space used by the program is O(n) for the queue data structure.
Also See:
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)