Friday, July 13, 2012

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; }
    void addNode(int data);
    int maxdepth(Node *node);
    int mindepth(Node *node);

private:
    void addNode(Node* node, int data);

private:
    Node* mRoot;
};

void Tree::addNode(int data) {
    if ( mRoot == NULL ) {
        Node* tmp = new Node();
        tmp->setData(data);
        mRoot = tmp;
    }
    else {
        addNode(mRoot, data);
    }
}

void Tree::addNode(Node* node, int data) {
    if ( data <= node->data() ) {
        if ( node->left() != NULL )
            addNode(node->left(), data);
        else {
            Node* tmp = new Node();
            tmp->setData(data);
            tmp->setParent(node);
            node->setLeft(tmp);
        }
    }
    else {
        if ( node->right() != NULL )
            addNode(node->right(), data);
        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();
    t->addNode(500);
    t->addNode(300);
    t->addNode(600);
    t->addNode(550);
    t->addNode(700);
    t->addNode(750);
    t->addNode(200);
    t->addNode(150);
    t->addNode(250);
    t->addNode(350);
    t->addNode(800);

    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

1 comment :

  1. Sir, please write a method or destructor to clear all the node allocated using new.

    ReplyDelete

Contact Form

Name

Email *

Message *

Back to Top