Print longest path in binary tree

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 classclass 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 classclass 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()));elsereturn 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 reachedprint_array(path, len);return;}print_largest_path(node->left(), path, len, depth);print_largest_path(node->right(), path, len, depth);}// Test programint 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