Thursday, February 24, 2022

Max of Generic Tree

I/P: 

12

10 20 -1 30 50 -1 60 -1 -1 40 -1 -1

O/P: 60




import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Stack;

public class Maximum_Of_GenericTree {

private static class Node {
int data;
ArrayList<Size_Of_GenericTree.Node> children = new ArrayList<>();
}

public static int max(Size_Of_GenericTree.Node node) {
int max = Integer.MIN_VALUE;
// FAITH: mere sare child apna max laa kr denge
for (Size_Of_GenericTree.Node child : node.children) {
int m = max(child);
max = Math.max(max, m);
}
// Expectation: hum parent (10) ko compare krenge with
// the max of all the children
max = Math.max(max, node.data);

return max;
}


public static void display(Size_Of_GenericTree.Node node) {
String str = node.data + " -> ";
for (Size_Of_GenericTree.Node child : node.children) {
str += child.data + ", ";
}
str += ".";
System.out.println(str);

for (Size_Of_GenericTree.Node child : node.children) {
display(child);
}
}

public static Size_Of_GenericTree.Node construct(int[] arr) {
Size_Of_GenericTree.Node root = null;

Stack<Size_Of_GenericTree.Node> st = new Stack<>();
for (int i = 0; i < arr.length; i++) {
if (arr[i] == -1) {
st.pop();
} else {
Size_Of_GenericTree.Node t = new Size_Of_GenericTree.Node();
t.data = arr[i];

if (st.size() > 0) {
st.peek().children.add(t);
} else {
root = t;
}

st.push(t);
}
}

return root;
}

public static int size(Size_Of_GenericTree.Node node) {
// write your code here
if (node == null) return 0;
int size = 0;
// Expectation: children apna size khud calculate kr lenge
// let 20,30,40 apni apni node ka count le aate hain
ArrayList<Size_Of_GenericTree.Node> children = node.children;
for (Size_Of_GenericTree.Node child : children)
size += size(child);

// end me 10 (parent) apna count +1 kr dega
return size + 1;
}

public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] arr = new int[n];
String[] values = br.readLine().split(" ");
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(values[i]);
}

Size_Of_GenericTree.Node root = construct(arr);
int sz = max(root);
System.out.println(sz);
// display(root);

}

}



No comments:

Post a Comment

Diagonal Traversal

 eg.  1       2       3       4 5      6       7       8 9    10    11     12 13  14   15    16 Output: 1 6 11 16 2 7 12 3 8 4  Approach:...