Convert hierarchy to nested objects – code

There are online tools that convert JSON file to objects. The same idea applies to “convert hierarchy to nested objects”. The syntax of nested object is obj.children[1].children[2]. “obj” is the top level object. Each nested object’s level maps with the level in the hierarchy list. You can access any object from top object “obj”.

Tree data structure is a hierarchy data structure. From root, you can access any node in the tree. Using the same concept, first we define a class “StatusNode”. It is like a TreeNode, in which there are links to its children”. The top object “obj” can be regarded as the root of the tree. When reading each item in the hierarchy list, it is like adding a node in a tree. To keep track the position where to add, we define two variables “prev” and “parent”. “pre” keeps track the previous added node’s level. “parent” keeps track the upper level node. It starts from root. By comparing the level of the new item with “prev”, we can decide where to add new object. Here are implementation of convert hierarchy to nested objects.

Microsoft Interview Question(CareerCup):
Design a data structure which reads below block of text
*Status update1
**Joe is working on a bug
**Alice is on vacation
*StatusUpdate2
**Alex finished task1
and returns me an Object such that I can navigate this nested text easily like this:

obj.children[0] – > returns “StatusUpdate”
obj.children[0].children[1] -> “Alice is on vacation”

Java Code:

Output:
Status update1
 Joe is working on a bug
 Alice is on vacation
Status Update2
 Alex finished task1

obj.children[0] – > Status update1
obj.children[0].children[1] -> Alice is on vacation

O Notation:
Time complexity: O(n)
Space complexity: O(1)


Download ConvertHierarchyToNestedObject.java
Build hierarchy tree

Comments are closed