Build hierarchy tree – Code

Build hierarchy tree reads employee data and build a corporation hierarchy tree from the list. HashMap plays important role to store the data when reading the input. The trick of this question is to find the root. You can get the root by finding the employee without the manager. Starting from the root, get subordinates for each employee. This way you the build tree recursively.

Here are the steps :
1. Define employee Class that has id, name and subordinates. the data line by line, store the data in the HashMap. If the employee doesn’t have managerId, he is at the top of hierarchy (root).
3. Use recursion to find subordinates and build nary tree.
4. Use recursion to print the hierarchy. The data structure tree and HashMap are used.

Amazon Interview Question:
Scan the file, it has empId, first names, last name, and reportToId.
Output a file to show the hierarchy, nobody to report to is at the top.
Input Sample:

Output Sample:

Java Code:

Joseph Grant
 Rob Choi
  Andy Zuckeman
  Mark O’Donnell
 Lois Lemer
  Melaney Partner
 Moises Medina
  Paul Marmolejo
  Christie Jacobs
  Cliff Gannett

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

If you have any questions or want to put comments, please post at youtube. I will answer you!
The code displayed here is the simplified version after the enhancement in the 2nd edition of Java coding interview pocket book. Please click the top download button to download the original version.

Build hierarchy tree tutorial
The complete list of coding interview questions

Comments are closed