From List to Immutable Hierarchy-Tree (with Scala)

As part of my job at <a href="https://www.hibob.com/" rel="noopener ugc nofollow" target="_blank">Hibob</a>, I’ve been looking for a way to construct an Organizational-Chart out of a list of employees. This article shows one approach to creating an immutable tree structure out of a list of hierarchical objects. <img alt="" src="https://miro.medium.com/v2/resize:fit:700/1*HMC1nJm4c83WbCIAutCt2A.png" style="height:316px; width:700px" /> Org-Chart / bob Our input is a list of employees — each employee entry has an “id” and “managerId” property. The managerId can be empty or reference another employee on the list as its manager. <img alt="" src="https://miro.medium.com/v2/resize:fit:700/1*QnWjlnGtp_RemNd1MdQ7Zg.png" style="height:329px; width:700px" /> List ⇒ Tree I googled my way as a good lazy citizen does and found some <a href="https://stackoverflow.com/questions/444296/how-to-efficiently-build-a-tree-from-a-flat-structure" rel="noopener ugc nofollow" target="_blank">efficient ways to do the job</a>. Basically, all the solutions I’ve found involve creating a “Node” object with an empty children array — then adding children to it on the fly pointing to other nodes. Adding children to a node object means we mutate this object after creation and therefore construct a tree made of mutable objects. This isn’t necessarily bad and depends on one’s needs, but I wanted to explore a way to construct nodes in an <a href="https://en.wikipedia.org/wiki/Immutable_object" rel="noopener ugc nofollow" target="_blank">Immutable</a> way without sacrificing much efficiency compared to mutable solutions. <a href="https://medium.com/hibob-engineering/from-list-to-immutable-hierarchy-tree-with-scala-c9e16a63cb89">Visit Now</a>