I am given a response in JSON format, where the PREORDER traversal of the n-ary tree is given in an JSONArray. I need to convert it to a tree structure and send back in response.
GIVEN the response
{
"ControllingArea" : "TZUS",
"TopNodes" : false,
"Language" : "EN",
"TONODES" : [
{
"Groupname" : "INC",
"Hierlevel" : 0,
"Valcount" : 0,
"Descript" : "INC"
},
{
"Groupname" : "INC-BBSR",
"Hierlevel" : 1,
"Valcount" : 0,
"Descript" : "INC1"
},
{
"Groupname" : "INC-STPI",
"Hierlevel" : 2,
"Valcount" : 0,
"Descript" : "INC2"
},
{
"Groupname" : "INC-FORT",
"Hierlevel" : 2,
"Valcount" : 0,
"Descript" : "INC3"
},
{
"Groupname" : "INC-BBL",
"Hierlevel" : 1,
"Valcount" : 0,
"Descript" : "INC4"
},
{
"Groupname" : "INC-PUNE",
"Hierlevel" : 1,
"Valcount" : 0,
"Descript" : "INC5"
}
],
"TOVALUE" : [
{
"Valfrom" : "",
"Valto" : ""
}
]
}
Here the TONODES Represent the Preorder traversal on the tree, ALSO the hierarchy level are given in the objects that which level it belongs to.
the tree should look like (UI View).
The Response I want to send should look like:
{
"INC": {
"Groupname": "INC",
"Hierlevel": 0,
"Valcount": 0,
"Descript": "INC",
"INC-BBSR": {
"Groupname": "INC-BBSR",
"Hierlevel": 1,
"Valcount": 0,
"Descript": "INC1",
"INC-STPI": {
"Groupname": "INC-STPI",
"Hierlevel": 2,
"Valcount": 0,
"Descript": "INC2"
},
"INC-FORT": {
"Groupname": "INC-FORT",
"Hierlevel": 2,
"Valcount": 0,
"Descript": "INC3"
}
},
"INC-BBL": {
"Groupname": "INC-BBL",
"Hierlevel": 1,
"Valcount": 0,
"Descript": "INC4"
},
"INC-PUNE": {
"Groupname": "INC-PUNE",
"Hierlevel": 1,
"Valcount": 0,
"Descript": "INC5"
}
}
}
I tried searching a lot on the web for generating N-Ary trees but not got any satisfactory results. Because the solution says if you know the n u will be able to make the tree, but I don't know the n here as it can have random.
I have also tried using stack to insert nodes to it if higher hierarchy level of object is coming and pop if lower hierarchy level of object is coming.
@Override
public ResponseDTO getTreeStructure(JSONObject sapResponse) {
JSONObject response = new JSONObject();
Stack<JSONObject> treeStack = new Stack<>();
JSONArray iteratingArray = sapResponse.getJSONArray("TONODES");
for(int i = 0 ; i < iteratingArray.length(); i++){
JSONObject tempObject= iteratingArray.getJSONObject(i);
if(treeStack.empty()) {
treeStack.push(tempObject);
response.put(tempObject.getString("Groupname"), tempObject);
}else if(treeStack.peek().getInt("Hierlevel") < tempObject.getInt("Hierlevel")){
response.getJSONObject(treeStack.peek().getString("Groupname")).put(tempObject.getString("Groupname"), tempObject);
treeStack.push(tempObject);
}else if(treeStack.peek().getInt("Hierlevel") >= tempObject.getInt("Hierlevel")){
while(!treeStack.empty() && treeStack.peek().getInt("Hierlevel") >= tempObject.getInt("Hierlevel")){
treeStack.pop();
}
response.getJSONObject(treeStack.peek().getString("Groupname")).put(tempObject.getString("Groupname"), tempObject);
treeStack.push(tempObject);
}
}
return new ResponseDTO(200, "ok", response);
//return null;
}
The problem is that I cannot get the previous object to push into the response. I cannot track down the parent nodes to get and reach the current Node to push.
0(N0) -> 1(N1) -> 2(N2)
response.getJSONObject(N0).getJSONObjectI(N1).put(N2.getString("Groupname"), N2);
But instead in my approach I am getting
response.getJSONObject(N1).put(N2)
I can get the node 1 from the top of the stack, but I cannot track down the parent 0th node to push the 2nd object under 1st.
If somehow it is possible to get the previous nodes as per hierarchy, I will be able to make the tree.
Please correct my code or tell me a better approach to solve this.
Please correct my code or tell me a better approach to solve this.
The Stack approach is definitely great for what you need to do, especially if you consider that the nodes in the given Json are always listed in order (each node is always preceded either by their parent or a sibling).
The only problem with your code lies in the bit response.getJSONObject(treeStack.peek().getString("Groupname")). Here, you're trying to retrieve the parent node from the Json you're building rather than from the Stack. Your Stack already has the parent node that you need at the top, just use treeStack.peek(). Furthermore, getJSONObject looks for an attribute identified by the given name only within the node. It won't further the search, descending in its nested JSONObject attributes.
Here is the tweaked version of your code:
public ResponseDTO getTreeStructure(JSONObject sapResponse) {
JSONObject response = new JSONObject();
Stack<JSONObject> treeStack = new Stack<>();
JSONArray iteratingArray = sapResponse.getJSONArray("TONODES");
for (int i = 0; i < iteratingArray.length(); i++) {
JSONObject tempObject = iteratingArray.getJSONObject(i);
if (treeStack.empty()) {
//When the tree is empty the current node is put as the root
response.put(tempObject.getString("Groupname"), tempObject);
treeStack.push(tempObject);
//Checking if the current node is a child of the previous node (the one at the top of the stack)
} else if (treeStack.peek().getInt("Hierlevel") < tempObject.getInt("Hierlevel")) {
// Retrieving the parent node from the stack with 'treeStack.peek()'
// instead of retrieving it from the json (response) with 'response.getJSONObject(treeStack.peek().getString("Groupname"))'
//
// The previous writing couldn't work, because getJSONObject() searches for an attribute identified by
// the given name only within the current node, it does NOT further the search in its JSONObject attributes.
// Furthermore, retrieving the parent node with getJSONObject() is redundant as the parent node is already
// at the top of the stack.
//
//Once the parent node is retrieved from the stack, the current node is added to it
treeStack.peek().put(tempObject.getString("Groupname"), tempObject);
treeStack.push(tempObject);
} else if (treeStack.peek().getInt("Hierlevel") >= tempObject.getInt("Hierlevel")) {
//Getting rid of the nodes with the same level (the siblings)
while (!treeStack.empty() && treeStack.peek().getInt("Hierlevel") >= tempObject.getInt("Hierlevel")) {
treeStack.pop();
}
//Adding the current node to the parent node
treeStack.peek().put(tempObject.getString("Groupname"), tempObject);
treeStack.push(tempObject);
}
}
return new ResponseDTO(200, "ok", response);
}
Here is also a live demo at OneCompiler where you can test the code.