How to find the minimum depth of a binary tree
The minimum depth of a binary tree is the number of nodes from the root node to the nearest leaf node.
Consider the binary tree below:
The minimum depth of this tree is ; it is comprised of nodes 1, 2, and 4.
Let’s look at solutions to calculate the minimum depth of a given binary tree.
1. Recursive solution
The idea is to check if every node is a leaf node. If the current node is a leaf node, return . Otherwise, if the node has no left sub-tree, then recur on the right sub-tree. Similarly, if the node has no right sub-tree, then recur on the left sub-tree. Finally, if a node has both left and right sub-trees, recur on both and return the minimum value.
Implementation
Using the binary tree illustrated above, the algorithm is implemented as follows:
#include <iostream>using namespace std;struct Node {int value;Node *left, *right;Node(int val){this->value = val;this->left = this->right = NULL;}};int minimumDepth(Node * curr){// Null node has 0 depth.if(!curr)return 0;// Leaf node reached.if (curr->left == NULL && curr->right == NULL)return 1;// Current node has only right subtree.if(!curr->left)return 1 + minimumDepth(curr->right);// Current node has only left subtree.else if (!curr->right)return 1 + minimumDepth(curr->left);// if none of the above cases, then recur on both left and right subtrees.return 1 + min(minimumDepth(curr->right),minimumDepth(curr->left));}// driver codeint main() {Node* root = new Node(1);root->left = new Node(2);root->right = new Node(3);root->left->left = new Node(4);root->right->left = new Node(5);root->right->right = new Node(6);root->right->right->left = new Node(8);root->right->left->right = new Node(7);cout << "The minumum depth is: " << minimumDepth(root) << endl;}
2. Level order traversal solution
Since all the nodes are traversed in the recursive solution described above, it has a time complexity of . However, note that even if the minimum depth is found immediately after the root node, the rest of the binary tree is still traversed.
The algorithm can be optimized further using the idea behind level-order traversal. Before reading ahead, spend some time thinking about how a level-order traversal can be used to optimize the minimum depth’s calculation.
In the binary tree illustrated earlier, the algorithm would stop once we reached node 4, so there would be no need to traverse nodes 5, 6,7, and 8.
Implementation
#include <iostream>#include <queue>using namespace std;struct Node {int value;Node *left, *right;Node(int val){this->value = val;this->left = this->right = NULL;}};struct queueItem {Node * node;int depth;};int minimumDepth(Node * root){// No depth if root is NULL.if (!root)return 0;// Initialise a queue of type "queueItem" defined above.queue <queueItem> q;// Push the root node into the queue with depth 1.queueItem currItem = {root, 1};q.push(currItem);// Level order traversal algorithm:while (!q.empty()){// Get the node at the front of the queuecurrItem = q.front();q.pop();// Retreive the data of the node.Node * node = currItem.node;int depth = currItem.depth;// If this is the first leaf node encountered,// return its depth and terminate the algorithm.if (node->left == NULL && node->right == NULL)return depth;// If left subtree exists, add it to queueif (node->left != NULL){queueItem newItem;newItem.node = node->left;newItem.depth = depth + 1;q.push(newItem);}// If right subtree exists, add it to queueif (node->right != NULL){queueItem newItem;newItem.node = node->right;newItem.depth = depth + 1;q.push(newItem);}}}// driver codeint main() {Node* root = new Node(1);root->left = new Node(2);root->right = new Node(3);root->left->left = new Node(4);root->right->left = new Node(5);root->right->right = new Node(6);root->right->right->left = new Node(8);root->right->left->right = new Node(7);cout << "The minumum depth is: " << minimumDepth(root) << endl;}
RELATED TAGS
