Each branch of the data structure is meticulously separated using recursion

Question

Each branch of the data structure is meticulously separated using recursion

I am struggling with a recursive data structure similar to the example provided below. My goal is for each branch, starting from null (parentTagId), to extend as far as the final one.

I have no clue on how to achieve this, so any suggestions would be greatly appreciated!

Original data:

[ 
  { TagId: 2, ParentTagId: null, Name: 'women' },
  { TagId: 5, ParentTagId: 2, Name: 'bottom' },
  { TagId: 4, ParentTagId: 2, Name: 'top' },
  { TagId: 7, ParentTagId: 4, Name: 'shirt' },
  { TagId: 8, ParentTagId: 4, Name: 'tshirt' },
  { TagId: 12, ParentTagId: 7, Name: 'longsleeve' },
  { TagId: 16, ParentTagId: null, Name: 'men' }
]

Expected outcome:

women > bottom  
women > top > shirt > longsleeve   
women > tshirt  
men

Output data:

[
  {
    path: [ 
      { TagId: 2, ParentTagId: null, Name: 'women' },
      { TagId: 5, ParentTagId: 2, Name: 'bottom' }
    ]
  },
  {
    path: [
      { TagId: 2, ParentTagId: null, Name: 'women' },
      { TagId: 4, ParentTagId: 2, Name: 'top' },
      { TagId: 7, ParentTagId: 4, Name: 'shirt' },
      { TagId: 12, ParentTagId: 7, Name: 'longsleeve' }
    ]
  },
  {
    path: [
      { TagId: 2, ParentTagId: null, Name: 'women' },
      { TagId: 4, ParentTagId: 2, Name: 'top' },
      { TagId: 8, ParentTagId: 4, Name: 'tshirt' }
    ]
  },
  {
    path: [
      { TagId: 16, ParentTagId: null, Name: 'men' }
    ]
  }
]

javascript arrays json recursion

Answer 1

Answer №1

Imagine your data input as a tree structure. The goal is to create the path to each individual leaf node. A leaf node is identified as a tag with a TagId that has no references as a ParentTagId in any other tag.

Here is a simplified approach:

Go through all tags and form a set (a list with unique elements) of all ParentTagId values. In this case, the set would include: [2,4,7].
To identify the leaf nodes, iterate through all tags and select the ones where the TagId is not found in the set obtained from step 1. For this dataset, those tags are: [5,8,12,16].
Create a function called getTagById to retrieve a tag based on its id.
Develop a recursive function to construct the path for each leaf node.
Process all leaf nodes by adding the result of getPath([], leaf) to an array named paths. This array will contain the paths to each leaf represented as arrays of tags.
Construct the final output using the information stored in paths.

Code snippet for step 1:

var parentTagIdSet = [];
for (var i = 0; i < originData.length; ++i) {
  var parentTagId = originData[i].ParentTagId;
  if (parentTagId != null && parentTagIdSet.indexOf(parentTagId) == -1) {
    parentTagIdSet.push(parentTagId);
  }
}

Code snippet for step 2:

var leaves = [];
for (var i = 0; i < originData.length; ++i) {
  var tag = originData[i];
  if (parentTagIdSet.indexOf(tag.TagId) == -1) {
    leaves.push(tag);
  }
}

Code snippet for step 3:

function getTagById(id) {
  for (var i = 0; i < originData.length; ++i) {
    var tag = originData[i];
    if (tag.TagId == id) {
      return tag;
    }
  }
  // Return null if the loop completes without finding a matching ParentTagId.
  return null;
}

Code snippet for step 4:

function getPath(path, currentTag) {
   if (currentTag == null) {
     // Reverse the path if incorrect ParentTagIds were encountered.
     path.reverse();
     return path;
   }
   path.push(currentTag);
   var parentId = currentTag.ParentTagId;
   if (parentId == null) {
     path.reverse();
     return path;
   } else {
     return getPath(path, getTagById(parentId));
   }
 }

Code snippet for step 5:

var paths = [];
for (var i = 0; i < leaves.length; ++i) {
  paths.push(getPath([], leaves[i]));
}

Answer 2

Imagine your data input as a tree structure. The goal is to create the path to each individual leaf node. A leaf node is identified as a tag with a TagId that has no references as a ParentTagId in any other tag.

Here is a simplified approach:

Go through all tags and form a set (a list with unique elements) of all ParentTagId values. In this case, the set would include: [2,4,7].
To identify the leaf nodes, iterate through all tags and select the ones where the TagId is not found in the set obtained from step 1. For this dataset, those tags are: [5,8,12,16].
Create a function called getTagById to retrieve a tag based on its id.
Develop a recursive function to construct the path for each leaf node.
Process all leaf nodes by adding the result of getPath([], leaf) to an array named paths. This array will contain the paths to each leaf represented as arrays of tags.
Construct the final output using the information stored in paths.

Code snippet for step 1:

var parentTagIdSet = [];
for (var i = 0; i < originData.length; ++i) {
  var parentTagId = originData[i].ParentTagId;
  if (parentTagId != null && parentTagIdSet.indexOf(parentTagId) == -1) {
    parentTagIdSet.push(parentTagId);
  }
}

Code snippet for step 2:

var leaves = [];
for (var i = 0; i < originData.length; ++i) {
  var tag = originData[i];
  if (parentTagIdSet.indexOf(tag.TagId) == -1) {
    leaves.push(tag);
  }
}

Code snippet for step 3:

function getTagById(id) {
  for (var i = 0; i < originData.length; ++i) {
    var tag = originData[i];
    if (tag.TagId == id) {
      return tag;
    }
  }
  // Return null if the loop completes without finding a matching ParentTagId.
  return null;
}

Code snippet for step 4:

function getPath(path, currentTag) {
   if (currentTag == null) {
     // Reverse the path if incorrect ParentTagIds were encountered.
     path.reverse();
     return path;
   }
   path.push(currentTag);
   var parentId = currentTag.ParentTagId;
   if (parentId == null) {
     path.reverse();
     return path;
   } else {
     return getPath(path, getTagById(parentId));
   }
 }

Code snippet for step 5:

var paths = [];
for (var i = 0; i < leaves.length; ++i) {
  paths.push(getPath([], leaves[i]));
}

Answer 3

Answer №2

It is crucial to have an object structured as shown below...

class Trie implements IteratorAggregate
{
    protected $parent;
    protected $children = [];

    public function insert(Node $node)
    {
        $node->parent     = $this;
        $this->children[] = $node;
    }

    public function findById($id)
    {
        foreach($this->children as $childNode) {
            if ($childNode->TagId === $id) {
                return $childNode;
            }
            if ($childNode->hasChildren()) {
                $n = $childNode->findById($id);
                if ($n) {
                   return $n;
                }
            }
        }
    }

    public function hasChildren()
    {
        return (bool) count($this->children);
    }

    public function getIterator()
    {
        return new ArrayIterator($this->children);
    }
}

Furthermore, consider the node structure...

class Node extends Trie
{
    public function __construct(stdClass $obj)
    {
        foreach($obj as $p => $v) {
            $this->$p = $v;
        }
    }
}

To properly organize your list of objects, iterate over each node's object and then insert those with a null parent id into the tree's root. For nodes with children, insert them directly into their respective parents.

For instance,

$list = json_decode(<<<'JSON'
[ 
  { "TagId": 2, "ParentTagId": null, "Name": "women" },
  { "TagId": 5, "ParentTagId": 2, "Name": "bottom" },
  { "TagId": 4, "ParentTagId": 2, "Name": "top" },
  { "TagId": 7, "ParentTagId": 4, "Name": "shirt" },
  { "TagId": 8, "ParentTagId": 4, "Name": "tshirt" },
  { "TagId": 12, "ParentTagId": 7, "Name": "longsleeve" },
  { "TagId": 16, "ParentTagId": null, "Name": "men" }
]
JSON
);

$trie = new Trie;
/* Insert all of the parentless nodes */
foreach($list as $n => $obj) {
    if (!$obj->ParentTagId) {
        $trie->insert(new Node($obj));
        unset($list[$n]);
    }
}

/* Insert all of the child nodes */
foreach($list as $n => $obj) {
    $p = $trie->findById($obj->ParentTagId);
    if ($p) {
        $p->insert(new Node($obj));
        unset($list[$n]);
    }
}

By iterating over $trie, you will have access to all the parent nodes. Subsequently, you can explore deeper into the hierarchy by iterating over their children.

Answer 4

It is crucial to have an object structured as shown below...

class Trie implements IteratorAggregate
{
    protected $parent;
    protected $children = [];

    public function insert(Node $node)
    {
        $node->parent     = $this;
        $this->children[] = $node;
    }

    public function findById($id)
    {
        foreach($this->children as $childNode) {
            if ($childNode->TagId === $id) {
                return $childNode;
            }
            if ($childNode->hasChildren()) {
                $n = $childNode->findById($id);
                if ($n) {
                   return $n;
                }
            }
        }
    }

    public function hasChildren()
    {
        return (bool) count($this->children);
    }

    public function getIterator()
    {
        return new ArrayIterator($this->children);
    }
}

Furthermore, consider the node structure...

class Node extends Trie
{
    public function __construct(stdClass $obj)
    {
        foreach($obj as $p => $v) {
            $this->$p = $v;
        }
    }
}

To properly organize your list of objects, iterate over each node's object and then insert those with a null parent id into the tree's root. For nodes with children, insert them directly into their respective parents.

For instance,

$list = json_decode(<<<'JSON'
[ 
  { "TagId": 2, "ParentTagId": null, "Name": "women" },
  { "TagId": 5, "ParentTagId": 2, "Name": "bottom" },
  { "TagId": 4, "ParentTagId": 2, "Name": "top" },
  { "TagId": 7, "ParentTagId": 4, "Name": "shirt" },
  { "TagId": 8, "ParentTagId": 4, "Name": "tshirt" },
  { "TagId": 12, "ParentTagId": 7, "Name": "longsleeve" },
  { "TagId": 16, "ParentTagId": null, "Name": "men" }
]
JSON
);

$trie = new Trie;
/* Insert all of the parentless nodes */
foreach($list as $n => $obj) {
    if (!$obj->ParentTagId) {
        $trie->insert(new Node($obj));
        unset($list[$n]);
    }
}

/* Insert all of the child nodes */
foreach($list as $n => $obj) {
    $p = $trie->findById($obj->ParentTagId);
    if ($p) {
        $p->insert(new Node($obj));
        unset($list[$n]);
    }
}

By iterating over $trie, you will have access to all the parent nodes. Subsequently, you can explore deeper into the hierarchy by iterating over their children.

Answer 5

Answer №3

This JavaScript code may not be the most efficient or visually appealing, but it gets the job done.

    
    var input = [ 
      { TagId: 2, ParentTagId: null, Name: 'women' },
      { TagId: 5, ParentTagId: 2, Name: 'bottom' },
      { TagId: 4, ParentTagId: 2, Name: 'top' },
      { TagId: 7, ParentTagId: 4, Name: 'shirt' },
      { TagId: 8, ParentTagId: 4, Name: 'tshirt' },
      { TagId: 12, ParentTagId: 7, Name: 'longsleeve' },
      { TagId: 16, ParentTagId: null, Name: 'men' }
    ]
    
    var output = []
    var path = []
    function drill(el){
      path.push(el)
      var val = input.filter(function(e){return e.ParentTagId === el.TagId})
      if(val.length > 0)
        val.forEach(drill)
      else {
          var e = path[0]
          while(e = findParent(e))
            path.unshift(e)
          output.push({
            path: path
          })
          path = []
          return
      }
    }
    function findParent(el){
    return input.filter(function(e){return e.TagId === el.ParentTagId})[0]
    }
    input.filter(function(e){return e.ParentTagId === null}).forEach(drill)
    console.log(output)

Answer 6

This JavaScript code may not be the most efficient or visually appealing, but it gets the job done.

    
    var input = [ 
      { TagId: 2, ParentTagId: null, Name: 'women' },
      { TagId: 5, ParentTagId: 2, Name: 'bottom' },
      { TagId: 4, ParentTagId: 2, Name: 'top' },
      { TagId: 7, ParentTagId: 4, Name: 'shirt' },
      { TagId: 8, ParentTagId: 4, Name: 'tshirt' },
      { TagId: 12, ParentTagId: 7, Name: 'longsleeve' },
      { TagId: 16, ParentTagId: null, Name: 'men' }
    ]
    
    var output = []
    var path = []
    function drill(el){
      path.push(el)
      var val = input.filter(function(e){return e.ParentTagId === el.TagId})
      if(val.length > 0)
        val.forEach(drill)
      else {
          var e = path[0]
          while(e = findParent(e))
            path.unshift(e)
          output.push({
            path: path
          })
          path = []
          return
      }
    }
    function findParent(el){
    return input.filter(function(e){return e.TagId === el.ParentTagId})[0]
    }
    input.filter(function(e){return e.ParentTagId === null}).forEach(drill)
    console.log(output)

Each branch of the data structure is meticulously separated using recursion

Answer №1

Answer №2

Answer №3

Similar questions

An unforeseen issue occurred while trying to access an indexed element ID

NPM is having trouble locating a shell script

Display Material Popup in Angular before user leaves the page

Why does the Element.style.left property keep rejecting my input value?

Using JMeter's Json Extractor to Parse Data from Multiple HTTP Requests

Incorporating Local Storage into a To-Do List Application

"Maximizing Efficiency: Chaining Several Actions Using the JavaScript Ternary Operator

React-Troubleshooting list items and keys: A comprehensive guide to resolving common issues

Is it possible for the codebehind plugin to have a custom access path ending with

What is the best way to display or hide specific tables depending on the button chosen?

Using Facebook authentication in React Native

Issue with Scrollspy Functionality in Bootstrap 4

Error: Gulp could not parse the module

Generating random objects in a straight line with Javascript and HTML5: A step-by-step guide

Can you clarify the meaning of 'this' in an AngularJS controller?

What does {``} denote in react-native programming?

Merge two arrays into a single array

What causes the error message "ng-model is undefined"?

Having difficulty submitting a form with ajax, while accomplishing the same task effortlessly without ajax

Setting up jsdoc on a computer with slow internet access can be a bit tricky, but with