Creating full hierarchy string from parent-child structure algorithm, recursion

Question

I am solving following task. There is a given hierarchy of elements. I have the lowest element (base) and I need to create full hierarchy string. I have a function, which returns parents of an element. That means I can ask for a parent, then parents of the parent, etc.

Example: B is Parent of A, [C1, C2] are parents of B, ...

In this example, the result should be array of 3 strings (lines 1,2,3), each containing the full hierarchy for the base element A.

This is my pseudocode function:

Function getAllParents (Element)

    ParentCount = getParentCount(Element)
    result = Element
    IF (ParentCount > 0) THEN
        FOR i = 0 to ParentCount
            ParentName = getParentName(Element, i)
            result =  result + "," + getAllParents(parent)
        NEXT
    END IF
    
    IF (ParentCount = 0) then       
        result =  result + &newLine
    END IF
    
    RETURN result

END Function

It gives me following result for my example:

A,B,C1,D1,E1 
C2,D2,E2  
E3

How to achieve desired result?:

A,B,C1,D1,E1
A,B,C2,D2,E2
A,B,C2,D2,E3

Answer 1

We must build the current line on the way in, and join the returned lines together as the result on the way out from the recursion. Here is a pseudo code :

Function getAllParents (line, Element)
    result = “”
    ParentCount = getParentCount(Element)
    IF (ParentCount > 0) THEN
        FOR i = 0 to ParentCount
            ParentName = getParentName(Element, i)
            result_i = getAllParents(copy(line)+”,”+ParentName, ParentName)
            result = result + result_i
        NEXT
    ELSE
        result = copy(line)+&newLine
    END IF
    
    RETURN result

END Function

A newline is added to the line each time a terminal node is reached, just like in your table.

We call it as getAllParents( “A”, “A”).

To better understand how it works, here is the function call flow for your example :

(“A”, “A”)
- (“A,B”, “B”)
- - (“A,B,C1”, “C1”)
- - - (“A,B,C1,D1”, “D1”)
- - - - (“A,B,C1,D1,E1”, “E1”)
- - (“A,B,C2”, “C2”)
- - - (“A,B,C2,D2”, “D2”)
- - - - (“A,B,C2,D2,E2”, “E2”)
- - - - (“A,B,C2,D2,E3”, “E3”)