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

user_7199785 0
Viewed 132

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, ...

Example

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
recursion algorithm
2 Answers

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”)
user_115630400

As you said yourself in the question description, the issue is the result type: "the result should be array."

Here's an example in JavaScript:

function getParentCount(el, ps){
  return ps[el] && ps[el].length
}

function getParentName(el, i, ps){
  return ps[el][i]
}
    
function getAllParents(el, ps){
  const ParentCount = getParentCount(el, ps)
  
  const result = []
  
  if (ParentCount > 0){
    for (let i=0; i<ParentCount; i++){
      const ParentName = getParentName(el, i, ps)
      const ParentPaths = getAllParents(ParentName, ps)
      
      for (let path of ParentPaths)
        result.push(el + "," + path)
    }
        
  } else {
    result.push(el)
  }
  
  return result
}

const parents = {
  A: ['B'],
  B: ['C1', 'C2'],
  C1: ['D1'],
  C2: ['D2'],
  D1: ['E1'],
  D2: ['E2', 'E3']
}

for (let path of getAllParents('A', parents))
  console.log(path)

user_20347870
Related