Finding Minimum Depth of Binary Tree in C++
In this article, we will learn how to find the minimum depth of a binary tree in C++ with the help of the code example.
The minimum distance between the root node and the left node in a binary tree is called its minimum depth.
Below is a given given example:
Input: 7 / \ 3 5 / \ 1 2 Output: The minimum depth of the given binary tree: 2 Exaplanation: 7 -> 5
Minimum Depth of Binary Tree in C++
We are going to solve this problem using a recursive approach.
1. At the very first, create a tree using struct.
2. After that, create a function minDepth and pass the root node as an argument.
- Now check the base case where the tree has no element i.e. root == NULL.
- Check whether the tree has only one element if true return 1.
- Now transverse through the right subtree and left subtree.
3. Finally, return the minimum depth between the right subtree and left subtree.
Below is the complete code:
#include <bits/stdc++.h> using namespace std; struct Node{ int data; struct Node *left; struct Node *right; }; int minDepth(Node *root){ if (root == NULL) return 0; if(root->left == NULL && root->right == NULL) return 1; if (!root->left) return minDepth(root->right)+1; if(!root->right) return minDepth(root->left)+1; return min(minDepth(root->left), minDepth(root->right))+1; } void inorder(Node* root){ if (root == NULL) return; inorder(root->left); cout<<root->data<<" "; inorder(root->right); } Node *newNode(int data){ Node *temp = new Node; temp->data = data; temp->left = temp->right = NULL; return temp; } int main(){ Node *root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->right = newNode(4); root->left->left = newNode(5); root->right->left = newNode(6); root->right->right = newNode(8); root->left->left->left = newNode(7); cout<<"The inorder of given binary tree: "; inorder(root); cout<<endl; cout<<"The minimum depth of the given binary tree is "<<minDepth(root); return 0; }
Output
The inorder of given binary tree: 7 5 2 4 1 6 3 8 The minimum depth of the given binary tree is 3 Exaplanation: 1 -> 2 -> 4 is one of the minimum depth.
Also, read
Leave a Reply