This article demonstrates how to transform a nested tree structure into a flat array representation using recursive traversal. This technique is commonly used for converting hierarchical data (such as exam modules, organizational charts, or file systems) into a linear format suitable for tabular display or sequential processing.

Original Tree Structure

Consider the following nested data structure representing examination sections witth their sub-modules:

const examSections = [
  {
    category: 1,
    name: 'Part 1: General Knowledge',
    qcount: 10,
    judgeFlag: 0,
    description: 'General knowledge assessment',
    children: [
      {
        category: 6,
        name: '1.1 Section Title',
        qcount: 10,
        judgeFlag: 0,
        description: null,
        children: [
          { category: 7, name: '1.1.1 Subsection', qcount: 5, judgeFlag: 0, description: null, children: null, level: 0 },
          { category: 8, name: '1.1.2 Subsection', qcount: 5, judgeFlag: 0, description: 'Header note', children: null, level: 0 },
        ],
        level: 0,
      },
    ],
    level: 0,
  },
  { category: 2, name: 'Part 2: Language Comprehension', qcount: 5, judgeFlag: 0, description: null, children: null, level: 0 },
  {
    category: 3,
    name: 'Part 3: Quantitative Reasoning',
    qcount: 10,
    judgeFlag: 0,
    description: null,
    children: [
      {
        category: 9,
        name: '3.1 Section Title',
        qcount: 5,
        judgeFlag: 0,
        description: 'Section header',
        children: [{ category: 11, name: '3.1.1 Subsection', qcount: 5, judgeFlag: 1, description: null, children: null, level: 0 }],
        level: 0,
      },
      {
        category: 10, name: '3.2 Section Title', qcount: 5, judgeFlag: 0, description: null,
        children: [
          { category: 7, name: '3.2.1 Subsection', qcount: 5, judgeFlag: 0, description: null, children: null, level: 0 },
          { category: 8, name: '3.2.2 Subsection', qcount: 5, judgeFlag: 0, description: 'Details here', children: null, level: 0 },
        ],
        level: 0
      },
    ],
    level: 0,
  },
  { category: 4, name: 'Part 4: Logical Reasoning', qcount: 0, judgeFlag: 0, description: null, children: null, level: 0 },
  { category: 5, name: 'Part 5: Data Analysis', qcount: 0, judgeFlag: 0, description: null, children: null, level: 0 },
];

Flattened Array Transformation

The following implementation uses depth-first traversal with a breadcrumb stack to track ancestry. When reaching leaf nodes (nodes without children), it captures the comlpete path from root to leaf:

function convertTreeToLinearFormat(hierarchyData) {
  const flattenedOutput = [];
  let ancestryChain = [];
  
  const processNodes = (nodes, depth = 1) => {
    nodes.forEach(node => {
      const hasChildren = Array.isArray(node.children) && node.children.length > 0;
      
      if (hasChildren) {
        ancestryChain.push({
          id: node.category,
          title: node.name,
          questionCount: node.qcount,
          depth
        });
        processNodes(node.children, depth + 1);
      } else {
        flattenedOutput.push({
          questionCount: node.qcount,
          breadcrumbs: ancestryChain.concat({
            id: node.category,
            title: node.name,
            questionCount: node.qcount,
            depth
          }),
          depth
        });
        ancestryChain = [];
      }
    });
    
    return flattenedOutput;
  };
  
  return processNodes(hierarchyData);
}

console.log(convertTreeToLinearFormat(examSections));

Key Implementation Details

• Stack-based Tracking: The ancestryChain array maintains the current path from root to the current node, creating a breadcrumb trail of parent nodes.
• Leaf Node Detection: The algorithm identifies terminal nodes by checking if the children property is null or empty, at which point it constructs the final record containing the accumulated path.
• Depth Tracking: The depth parameter increments with each recursive call, providing metadata about the nesting level of each element.
• Path Reset: After processing each leaf node, the ancestry chain is cleared to prepare for the next branch traversal.