Get all the descendant nodes of one tree node

readme.md

Compile this file with C++ 11

g++ -std=c++0x GetAllDescendantsOfNode.cpp

Output

>>> Get all descendant nodes of node: 0
   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
>>> Get all descendant nodes of node: 1
   3   4   5   7   8   9  10  11
>>> Get all descendant nodes of node: 2
   6  12  13  14  15
>>> Get all descendant nodes of node: 3
   7   8
>>> Get all descendant nodes of node: 4
   9  10  11
>>> Get all descendant nodes of node: 5

>>> Get all descendant nodes of node: 6
  12  13  14  15

GetAllDescendantsOfNode.cpp

#include <iostream> // std::cout
#include <iomanip>  // std::setw()
#include <vector>   // std::vector

std::vector<int> getDescendants(std::vector<std::vector<int>> tree, int node){
  std::vector<int> descendants;
  descendants.insert(descendants.end(), tree[node].begin(), tree[node].end());
  for(int i = 0 ; i < descendants.size() ; i++){
    if( descendants[i] < tree.size() && !tree[descendants[i]].empty() ){
      //append
      descendants.insert(descendants.end(),
                         tree[descendants[i]].begin(),
                         tree[descendants[i]].end());
    }
  }
  return descendants;
}

void printDescendants(std::vector<std::vector<int>> tree, int node){
  std::vector<int> d = getDescendants(tree, node);
  for(int i = 0 ; i < d.size() ; i++){
    std::cout << std::setw(4) << d[i];
  }
  std::cout << std::endl;
}

void printAllDescendantsOfEveryNode(std::vector<std::vector<int>> tree){
  for(int i = 0 ; i < tree.size() ; i++){
    std::cout << ">>> Get all descendant nodes of node: " << i << std::endl;
    printDescendants(tree, i);
  }
}

int main(){

  /* Construct the tree:
   *
   *               0
   *              / \
   *             /   \
   *            /     \
   *           /       \
   *          /         \
   *         /           \
   *        1             2
   *       /  \           |
   *      /    \          |
   *     3      4         5
   *    /\     /|\      / /\ \
   *   /  \   / | \    / /  \ \
   *  7   8  9 10 11 12 13 14 15
   */

  // The following initialization is introduced in c++11
  std::vector<std::vector<int>> tree{
    {1, 2},
    {3, 4, 5},
    {6},
    {7, 8},
    {9, 10, 11},
    {},
    {12, 13, 14, 15}
  };

  printAllDescendantsOfEveryNode(tree);

  return 0;
}