Friday, July 13, 2012
Write a program to print longest path in binary tree.

The approach:-
  1. Initialize an array with size as maximum depth of the tree.

  2. Fill the node details in this array as we traverse the tree.

  3. If a path is reached with maximum depth print the path and return.

  4. Recursively scan the left and right sub tree.

The solution:-
#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);
    void print_largest_path(Node* node, int* path,
                            int len, int depth);

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

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;
}

void Tree::print_array(int* path, int len) {
    for ( int i = 0; i < len; i++ )
        cout << path[i] << " ";
    cout << endl;
}

void Tree::print_largest_path(Node* node, int* path, int len, int depth) {
    if ( node == NULL ) return;

    path[len] = node->data();
    len++;
    depth--;

    if ( depth == 0 ) {
        // max depth reached
        print_array(path, len);
        return;
    }

    print_largest_path(node->left(), path, len, depth);
    print_largest_path(node->right(), path, len, depth);
}

// 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);

    int d = t->maxdepth(t->root());
    int* path = (int*) malloc(sizeof(int) * d);
    int len = 0;
    t->print_largest_path(t->root(), path, len, d);

    delete path;
    delete t;
}


Output:-
500 600 700 750 800

3 comments :

  1. This comment has been removed by a blog administrator.

    ReplyDelete
  2. Longest Path is
    150 200 300 500 600 700 750 800
    is n't?

    ReplyDelete
    Replies
    1. It is the longest past starting from root.
      Hence, 500 600 700 750 800 is correct.

      Delete

Contact Form

Name

Email *

Message *

Back to Top