Build nested object from hierarchical list- code

Similar to convert JSON file to objects, we can covert hierarchical list to a nested object. The input is like a table of content with multiple levels, the output is a nested object 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, we define a “Node”. 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.

Microsoft Interview Question:
Design a data structure which reads below block of text
*Status update1
**Joe is working on a bug
**Alice is on vacation
**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:

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)

Build hierarchy tree

Comments are closed