title: Hierarchical data: efficiently build a list of every descendant for each node
body: <p>I have a two column data set depicting multiple child-parent relationships that form a large tree. I would like to use this to build an updated list of every descendant for each node. </p>
  
  <h3>Original Input:</h3>
  
  <pre><code>   child  parent
  1   2010    1000
  7   2100    1000
  5   2110    1000
  3   3000    2110
  2   3011    2010
  4   3033    2100
  0   3102    2010
  6   3111    2110
  </code></pre>
  
  <h3>Graphical depiction of relationships:</h3>
  
  <p><a href="https://i.stack.imgur.com/O3lhx.jpg" rel="noreferrer"><img src="https://i.stack.imgur.com/O3lhx.jpg" alt="example-data-relationship-tree"></a></p>
  
  <h3>Expected output:</h3>
  
  <pre><code>    descendant  ancestor
  0         2010      1000
  1         2100      1000
  2         2110      1000
  3         3000      1000
  4         3011      1000
  5         3033      1000
  6         3102      1000
  7         3111      1000
  8         3011      2010
  9         3102      2010
  10        3033      2100
  11        3000      2110
  12        3111      2110
  </code></pre>
  
  <p>Originally I decided to use a recursive solution with DataFrames. It works as intended, but Pandas is awfully inefficient. My research has led me to believe that an implementation using NumPy arrays (or other simple data structures) would be much faster on large data sets (of 10's of thousands of records).</p>
  
  <h3>Solution using data frames:</h3>
  
  <pre><code>import pandas as pd
  
  df = pd.DataFrame(
      {
          'child':     [3102, 2010, 3011, 3000, 3033, 2110, 3111, 2100],
          'parent':    [2010, 1000, 2010, 2110, 2100, 1000, 2110, 1000]
      },  columns=['child', 'parent']
  )
  
  
  def get_ancestry_dataframe_flat(df):
  
      def get_child_list(parent_id):
  
          list_of_children = list()
          list_of_children.append(df[df['parent'] == parent_id]['child'].values)
  
          for i, r in df[df['parent'] == parent_id].iterrows():
              if r['child'] != parent_id:
                  list_of_children.append(get_child_list(r['child']))
  
          # flatten list
          list_of_children = [item for sublist in list_of_children for item in sublist]
          return list_of_children
  
      new_df = pd.DataFrame(columns=['descendant', 'ancestor']).astype(int)
      for index, row in df.iterrows():
          temp_df = pd.DataFrame(columns=['descendant', 'ancestor'])
          temp_df['descendant'] = pd.Series(get_child_list(row['parent']))
          temp_df['ancestor'] = row['parent']
          new_df = new_df.append(temp_df)
  
      new_df = new_df\
          .drop_duplicates()\
          .sort_values(['ancestor', 'descendant'])\
          .reset_index(drop=True)
  
      return new_df
  </code></pre>
  
  <p>Because using pandas DataFrames in this way is very inefficient on large data sets, <strong>I need to improve the performance of this operation.</strong> My understanding is that this can be done by using more efficient data structures better suited for looping and recursion. I want to perform this same operation in the most efficient way possible. </p>
  
  <p>Specifically, I'm asking for <strong>optimization of speed.</strong></p>