﻿ Find the minimum depth of binary search tree and maximum depth of binary search tree ~ Programming Tutorials by SourceTricks
Friday, July 13, 2012

## Find the minimum depth of binary search tree and maximum depth of binary search tree

### Write a program to find the minimum depth of binary search tree and maximum depth of binary search tree

The approach:-
1. Depth is the height of a leaf node starting from the root.
2. Easiest approach is to have recursive function which finds the depth of left and write sub trees.

#### C++ program to find the minimum depth of binary search tree and maximum depth of binary search tree

```#include <iostream>
#include <cstdlib>
using namespace std;

// Node class
class Node {
public:
Node() { mData = -1; mParent = NULL; mLeft = NULL; mRight = NULL; }
~Node() {}
int data() { return mData; }
void setData(int data) { mData = data; }
Node* left() { return mLeft; }
void setLeft(Node* left) { mLeft = left; }
Node* right() { return mRight; }
void setRight(Node* right) { mRight = right; }
Node* parent() { return mParent; }
void setParent(Node* parent) { mParent = parent; }
private:
int mData;
Node* mLeft;
Node* mRight;
Node* mParent;
};

// Tree class
class Tree {
public:
Tree() { mRoot = NULL; }
~Tree() {}
Node* root() { return mRoot; }
int maxdepth(Node *node);
int mindepth(Node *node);

private:

private:
Node* mRoot;
};

if ( mRoot == NULL ) {
Node* tmp = new Node();
tmp->setData(data);
mRoot = tmp;
}
else {
}
}

void Tree::addNode(Node* node, int data) {
if ( data <= node->data() ) {
if ( node->left() != NULL )
else {
Node* tmp = new Node();
tmp->setData(data);
tmp->setParent(node);
node->setLeft(tmp);
}
}
else {
if ( node->right() != NULL )
else {
Node* tmp = new Node();
tmp->setData(data);
tmp->setParent(node);
node->setRight(tmp);
}
}
}

int Tree::maxdepth(Node *node) {
if ( node )
return 1 + std::max(maxdepth(node->left()), maxdepth(node->right()));
else
return 0;
}

int Tree::mindepth(Node *node) {
if ( node )
return 1 + std::min(mindepth(node->left()), mindepth(node->right()));
else
return 0;
}

// Test program
int main() {
Tree* t = new Tree();

cout << "Max depth = " << t->maxdepth(t->root()) << endl;
cout << "Min depth = " <<t->mindepth(t->root()) << endl;

delete t;
}```

Output:-
```Max depth = 5
Min depth = 3```

Name

Email *

Message *