You are not logged in. Please login at www.codechef.com to post your questions!

×

Not getting output of this c++ program to find height of any tree

 class Node {
 public:
 int value;
 std::vector<int> children;
 Node(int value) {
    this->value=value;
}

void add_child(int child) {
    this->children.push_back(child);
}

int get_size() {
    return (this->children.size());
}
};

class Tree {
private:
int number_of_nodes;
Node *root;
std::vector<int> parents;
std::map<int, Node *> nodes;

void construct_tree() {
    for (int i = 0; i < this->number_of_nodes; i++) {
        this->nodes[i] = new Node (i);
    }
    for (int i = 0; i < this->number_of_nodes; i++) {

        int parent = this->parents[i];

        if (parent == -1) {
            this->root = this->nodes[i];
        } 
        else {
            this->nodes[parent]->add_child(i);
        }  ;
    }
}

int get_max_height(Node *node) {
    if (node == NULL) return 0; // this ain't shit
    if (node->get_size() == 0) return 1; // no children

    int height = 0;
    for (int i = 0; i < node->get_size(); i++) {
        int height_of_this_child = this->get_max_height(this->nodes[node->children[i]]);
        height = max(height, height_of_this_child);
    }

    return (height + 1);
}

public:

// reading the tree
void read() {
    cin >> this->number_of_nodes;
    this->parents.resize(this->number_of_nodes);
    for (int i = 0; i < this->number_of_nodes; i++) {
        cin >> this->parents[i];
    }

}

int get_height() {
    this->construct_tree();

    cout<<"tree construction done"<<endl;

    return(this->get_max_height(this->root));
}

};


int main() {

Tree *t1 = new Tree();
t1->read();
cout << t1->get_height() << endl;


return 0;
}

asked 14 Dec '18, 17:17

jojiiiii's gravatar image

0★jojiiiii
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,901
×1,391
×57

question asked: 14 Dec '18, 17:17

question was seen: 36 times

last updated: 14 Dec '18, 17:17