I have been getting quite a bit of feedback interpreting this article to mean that recursive functions are bad and iterative methods are always better. This couldn’t be further from what I believe — This article simply aims to discuss iteration as an alternative tool! Edit: In programming, we’re often faced with situations where the answer appears to require solving the same problem an indeterminate number of times. When we encounter a problem like this, we tend to reach for recursion — often accomplished by creating a function that calls itself as many times as necessary. Recursion is extremely important in programming and many problems can only be solved by using it. That being said, recursion can be slower, fill up the call stack, and can be conceptually trickier. In this post, I will explore an example of a problem that seems to lend itself to a recursive solution, but can in fact be solved more efficiently through an understanding of JavaScript object references. The motivation for this post example came from an excellent that I have adapted. StackOverflow answer The Problem In this problem, we are attempting to build a hierarchical object tree structure based on a flat array of objects. We do not know ahead of time how deep the tree will be, but we know that each node can only have one parent and can have any number of children. A visualization of an example tree we can work with is as follows: (Example Tree Structure) As mentioned, the data we receive to build this tree example is a flattened array in the following format. Each element represents one node of the tree and can be the child of only one parent node. Node 8 has no parent, so we can see in the array below that the object for 8 has a equal to . id parentId null const flat = [
  { id: , parentId: },
  { id: , parentId: },
  { id: , parentId: },
  { id: , parentId: },
  { id: , parentId: },
  { id: , parentId: },
  { id: , parentId: }, 
  { id: , parentId: },
  { id: , parentId: }
] 1 3 3 8 4 6 6 3 7 6 8 null 10 8 13 14 14 10 The final structure we need to rearrange this flat array into is as follows: [
  { 
    id: ,
    children: [
      { 
        id: , 
        children: [
          { 
            id: , 
            children: [] 
          }, 
          { 
            id: , 
            children: [ 
              { id: , children: [] }, 
              { id: , children: [] } 
            ]
          }
        ] 
      },
      { 
        id: , 
        children: [ 
          { 
            id: , 
            children: [
              { id: , children: [] }
            ] 
          }
        ]
      }
    ]
  }
] 8 3 1 6 4 7 10 14 13 The Solution Your first inkling in this scenario might be to reach for recursion: we’re given a tree of indeterminate length. We imagine we might have to create a function that populates a node’s children. Then, we recursively call that function until the tree is fully populated and (i.e., no more child nodes are found). While this would probably work, there is a better way! We can simply iterate through the array and assign each object to the array of its parent object. This may not make intuitive sense, but consider this logic: children Object is assigned to the array of object 3 children 8 Object is assigned to the array of object 6 children 3 The Object that was assigned to the array of object is really just a to Object in memory… meaning its array will have the Object reference. 3 children 8 reference 3 children 6 This logic extends to the entire array, meaning we just need to go through the array once to build out our tree! Here is a potential non-recursive solution based on this idea: flat = [
  { : , : },
  { : , : },
  { : , : },
  { : , : },
  { : , : },
  { : , : },
  { : , : }, 
  { : , : },
  { : , : }
] root = [];

flat.forEach( { (!node.parentId) root.push(node); parentIndex = flat.findIndex( el.id === node.parentId); (!flat[parentIndex].children) { flat[parentIndex].children = [node];
  }
  
  flat[parentIndex].children.push(node);
}); .log(root); const id 1 parentId 3 id 3 parentId 8 id 4 parentId 6 id 6 parentId 3 id 7 parentId 6 id 8 parentId null id 10 parentId 8 id 13 parentId 14 id 14 parentId 10 // Create root for top-level node(s) const => node // No parentId means top level if return // Insert node as child of parent in flat array const => el if return console Nice and simple, and we only iterate through the array once! There is one bonus optimization I would like to make: the function we use each time through the loop isn’t a big deal for the small example tree, but this could actually get expensive if we’re working with a large tree. Let’s create an object to cache found parent locations. findIndex root = []; map = {};

flat.forEach( { (!node.parentId) root.push(node); parentIndex = map[node.parentId]; ( parentIndex !== ) {
    parentIndex = flat.findIndex( el.id === node.parentId);
    map[node.parentId] = parentIndex;
  } (!flat[parentIndex].children) { flat[parentIndex].children = [node];
  }
  
  flat[parentIndex].children.push(node);
}); .log(root); // Create root for top-level node(s) const // Cache found parent index const => node // No parentId means top level if return // Insert node as child of parent in flat array let if typeof "number" => el if return console Success! We have accomplished our tree build without implementing a recursive function.

You Might Not Need that Recursive Function in JavaScript

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Untitled Story

12 JavaScript Concepts That Will Level Up Your Development Skills

10 Things Everyone Should Know About Machine Learning

10 Repositories that Will Transform the Way You Approach Technical Interviews

10 (Free) Data Structure and Algorithm Courses Junior Developers Should Explore

10 Data Structure & Algorithms Books Every Programmer Should Read

12 JavaScript Concepts That Will Level Up Your Development Skills

10 Things Everyone Should Know About Machine Learning

10 Repositories that Will Transform the Way You Approach Technical Interviews

10 (Free) Data Structure and Algorithm Courses Junior Developers Should Explore

10 Data Structure & Algorithms Books Every Programmer Should Read

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps