StackStalk
  • Home
  • Java
    • Java Collection
    • Spring Boot Collection
  • Python
    • Python Collection
  • C++
    • C++ Collection
    • Progamming Problems
    • Algorithms
    • Data Structures
    • Design Patterns
  • General
    • Tips and Tricks

Friday, July 13, 2012

Print longest path in binary tree

 July 13, 2012     Programming problems in CPP     No comments   

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
  • Share This:  
Newer Post Older Post Home

0 comments:

Post a Comment

Follow @StackStalk
Get new posts by email:
Powered by follow.it

Popular Posts

  • Avro Producer and Consumer with Python using Confluent Kafka
    In this article, we will understand Avro a popular data serialization format in streaming data applications and develop a simple Avro Produc...
  • Monitor Spring Boot App with Micrometer and Prometheus
    Modern distributed applications typically have multiple microservices working together. Ability to monitor and manage aspects like health, m...
  • Server-Sent Events with Spring WebFlux
    In this article we will review the concepts of server-sent events and work on an example using WebFlux. Before getting into this article it ...
  • Implement caching in a Spring Boot microservice using Redis
    In this article we will explore how to use Redis as a data cache for a Spring Boot microservice using PostgreSQL as the database. Idea is to...
  • Python FastAPI microservice with Okta and OPA
    Authentication (AuthN) and Authorization (AuthZ) is a common challenge when developing microservices. In this article, we will explore how t...
  • Spring Boot with Okta and OPA
    Authentication (AuthN) and Authorization (AuthZ) is a common challenge when developing microservices. In this article, we will explore how t...
  • Getting started with Kafka in Python
    This article will provide an overview of Kafka and how to get started with Kafka in Python with a simple example. What is Kafka? ...
  • Getting started in GraphQL with Spring Boot
    In this article we will explore basic concepts on GraphQL and look at how to develop a microservice in Spring Boot with GraphQL support. ...

Copyright © StackStalk