« Next larger node with value just greater than n.

Next larger

Given a generic tree and an integer n. Find and return the node with next larger element in the tree i.e. find a node with value just greater than n.

Note:

Return NULL if no node is present with the value greater than n.

Input format :

The first line of input contains data of the nodes of the tree in level order form. The order is: data for root node, number of children to root node, data of each of child nodes and so on and so forth for each node. The data of the nodes of the tree is separated by space.
The following line contains an integer, that denotes the value of n.

Output format :

The first and only line of output contains data of the node, whose data is just greater than n.

Constraints:

Time Limit: 1 sec

Sample Input 1 :

10 3 20 30 40 2 40 50 0 0 0 0

18

Sample Output 1 :

20

Sample Input 2 :

10 3 20 30 40 2 40 50 0 0 0 0

21

Sample Output 2:

30

Copy
1#include <iostream>
2#include <queue>
3#include <vector>
4#include<climits>
5using namespace std;
6
7template <typename T>
8class TreeNode {
9   public:
10    T data;
11    vector<TreeNode<T>*> children;
12
13    TreeNode(T data) { this->data = data; }
14
15    ~TreeNode() {
16        for (int i = 0; i < children.size(); i++) {
17            delete children[i];
18        }
19    }
20};
21
22TreeNode<int>* getNextLargerElement(TreeNode<int>* root, int x) {
23    if(root == NULL){
24        return NULL;
25    }
26
27    TreeNode<int>* ansNode = NULL;
28    int ans = INT_MAX;
29
30    for(int i=0; i<root->children.size(); i++){
31        TreeNode<int>* currAns = getNextLargerElement(root->children[i], x);
32        if(currAns != NULL && currAns->data < ans && currAns->data > x){
33            ansNode = currAns;
34            ans = currAns->data;
35        }
36    }
37
38    if(root->data < ans && root->data > x){
39        ansNode = root;
40        ans = root->data;
41    }
42
43    return ansNode;
44}
45
46TreeNode<int>* takeInputLevelWise() {
47    int rootData;
48    cin >> rootData;
49    TreeNode<int>* root = new TreeNode<int>(rootData);
50
51    queue<TreeNode<int>*> pendingNodes;
52
53    pendingNodes.push(root);
54    while (pendingNodes.size() != 0) {
55        TreeNode<int>* front = pendingNodes.front();
56        pendingNodes.pop();
57        int numChild;
58        cin >> numChild;
59        for (int i = 0; i < numChild; i++) {
60            int childData;
61            cin >> childData;
62            TreeNode<int>* child = new TreeNode<int>(childData);
63            front->children.push_back(child);
64            pendingNodes.push(child);
65        }
66    }
67
68    return root;
69}
70
71int main() {
72    TreeNode<int>* root = takeInputLevelWise();
73    int x;
74    cin >> x;
75    TreeNode<int>* ans = getNextLargerElement(root, x);
76
77    if (ans != NULL) {
78        cout << ans->data;
79    }
80}