forked from reachanihere/Data-Structures-and-Algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
/
MaxNodeInTree.cpp
103 lines (75 loc) · 2.15 KB
/
MaxNodeInTree.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
/*
Given a generic tree, find and return the node with maximum data. You need to return the complete node which is having maximum data.
Return null if tree is empty.
Input format :
Elements in level order form separated by space (as per done in class). Order is -
Root_data, n (No_Of_Child_Of_Root), n children, and so on for every element
Output Format :
Node with largest data
Sample Input :
10 3 20 30 40 2 40 50 0 0 0 0
Sample Output :
50
*/
#include <iostream>
using namespace std;
#include <vector>
template <typename T>
class TreeNode {
public:
T data;
vector<TreeNode<T>*> children;
TreeNode(T data) {
this->data = data;
}
~TreeNode() {
for (int i = 0; i < children.size(); i++) {
delete children[i];
}
}
};
TreeNode<int>* maxDataNode(TreeNode<int>* root) {
/* Don't write main().
* Don't read input, it is passed as function argument.
* Return output and don't print it.
* Taking input and printing output is handled automatically.
*/
if(root==NULL)
return NULL;
TreeNode <int>* cur=root;
for(int i=0;i<root->children.size();i++){
TreeNode<int>* desc=maxDataNode(root->children[i]);
if(cur->data<desc->data)
cur=desc;
}
return cur;
}
#include <queue>
TreeNode<int>* takeInputLevelWise() {
int rootData;
cin >> rootData;
TreeNode<int>* root = new TreeNode<int>(rootData);
queue<TreeNode<int>*> pendingNodes;
pendingNodes.push(root);
while (pendingNodes.size() != 0) {
TreeNode<int>* front = pendingNodes.front();
pendingNodes.pop();
int numChild;
cin >> numChild;
for (int i = 0; i < numChild; i++) {
int childData;
cin >> childData;
TreeNode<int>* child = new TreeNode<int>(childData);
front->children.push_back(child);
pendingNodes.push(child);
}
}
return root;
}
int main() {
TreeNode<int>* root = takeInputLevelWise();
TreeNode<int>* ans = maxDataNode(root);
if(root != NULL) {
cout << ans -> data;
}
}