Tail recursive JSON constructor

Question

I have a directory structure from NPM package 'directory-tree' that I would like to flatten into a simpler nested structure. I want a tail recursive solution to convert the first object into the second, but I'm having trouble wrapping my head around how to construct it.

Of course the primary conditional is whether or not a 'node' in the first structure is a 'file' or a 'directory'. If it's a file, we simply want the basename of the file to key the relative path. However, if it's a directory, we want the basename of the directory to key an object and recurse down frome there.

I'll use their example to illustrate the structure:

{
  "path": "photos",
  "name": "photos",
  "size": 600,
  "type": "directory",
  "children": [
    {
      "path": "photos/summer",
      "name": "summer",
      "size": 400,
      "type": "directory",
      "children": [
        {
          "path": "photos/summer/june",
          "name": "june",
          "size": 400,
          "type": "directory",
          "children": [
            {
              "path": "photos/summer/june/windsurf.jpg",
              "name": "windsurf.jpg",
              "size": 400,
              "type": "file",
              "extension": ".jpg"
            }
          ]
        }
      ]
    },
    {
      "path": "photos/winter",
      "name": "winter",
      "size": 200,
      "type": "directory",
      "children": [
        {
          "path": "photos/winter/january",
          "name": "january",
          "size": 200,
          "type": "directory",
          "children": [
            {
              "path": "photos/winter/january/ski.png",
              "name": "ski.png",
              "size": 100,
              "type": "file",
              "extension": ".png"
            },
            {
              "path": "photos/winter/january/snowboard.jpg",
              "name": "snowboard.jpg",
              "size": 100,
              "type": "file",
              "extension": ".jpg"
            }
          ]
        }
      ]
    }
  ]
}

I'd like the final structure to be much simpler. Something like the following:

{
    "photos": {
        "summer": {
            "june": {
                "windsurf.jpg": "photos/summer/june/windsurf.jpg"
            }
        },
        "winter": {
            "january": {
                "ski.png": "photos/winter/january/ski.png",
                "snowboard.jpg": "photos/winter/january/snowboard.jpg"
            }
        }
    }
}

I dont see any advantage of your "simple" structure. And i dont think that its possible to use tail call recursion here. — Jonas Wilms
– Jonas Wilms, Commented Jan 15, 2018 at 15:57
Why are you concerned with reshaping your data? Your proposed result is substantially worse than the original due to value-based keys. What will you do with the data after you reshape it? Display a list of files and directories? Search for files matching a string? That is your real question, not whatever you wrote here. — Mulan
– Mulan, Commented Jan 15, 2018 at 23:05
Sorry, I asked a technical question. Not advice on how to write my program. My real question is exactly as I have wrote and worded it. The thing with StackOverflow my friend, is that if you write a question on style or algorithmic approach, it's 'too general' and will be ignored or removed. If you write a question that's too idiosyncratic or library specific, it won't get any views. Please trust that some of us know this site isn't a place for CS101 kids to get advice on their homework. I don't need to explain what my program does and why this data structure needs to be the way it is. — W4t3randWind
– W4t3randWind, Commented Mar 26, 2018 at 17:16

גלעד ברקן · Accepted Answer · 2018-01-16 11:53:03Z

2

We can convert a depth-first search to tail-recursion for your case.

let testObj = {
  "path": "photos",
  "name": "photos",
  "size": 600,
  "type": "directory",
  "children": [
    {
      "path": "photos/summer",
      "name": "summer",
      "size": 400,
      "type": "directory",
      "children": [
        {
          "path": "photos/summer/june",
          "name": "june",
          "size": 400,
          "type": "directory",
          "children": [
            {
              "path": "photos/summer/june/windsurf.jpg",
              "name": "windsurf.jpg",
              "size": 400,
              "type": "file",
              "extension": ".jpg"
            }
          ]
        }
      ]
    },
    {
      "path": "photos/winter",
      "name": "winter",
      "size": 200,
      "type": "directory",
      "children": [
        {
          "path": "photos/winter/january",
          "name": "january",
          "size": 200,
          "type": "directory",
          "children": [
            {
              "path": "photos/winter/january/ski.png",
              "name": "ski.png",
              "size": 100,
              "type": "file",
              "extension": ".png"
            },
            {
              "path": "photos/winter/january/snowboard.jpg",
              "name": "snowboard.jpg",
              "size": 100,
              "type": "file",
              "extension": ".jpg"
            }
          ]
        }
      ]
    }
  ]
};

function tailRecurse(stack, result){
  if (!stack.length)
    return result;
    
  // stack will contain
  // the next object to examine
  [obj, ref] = stack.pop();

  if (obj.type == 'file'){
    ref[obj.name] = obj.path;
      
  } else if (obj.type == 'directory'){
    ref[obj.name] = {};
    
    for (let child of obj.children)
      stack.push([child, ref[obj.name]]);
  }
  
  return tailRecurse(stack, result);
}


// Initialise
let _result = {};
let _stack = [[testObj, _result]];

console.log(tailRecurse(_stack, _result));

answered Jan 16, 2018 at 11:53

גלעד ברקן

24k3 gold badges29 silver badges64 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

W4t3randWind Over a year ago

Very elegant passing by reference.... I wouldn't have thought to do that.

גלעד ברקן Over a year ago

@W4t3randWind thanks! That kind of stack implementation is often seen just as a while (stack.length) loop. Making it an explicit recursion is just another way of running the same thing really :)

Jonas Wilms · Accepted Answer · 2018-01-15 16:08:34Z

1

function copyNode(node, result = {}){
   if(node.type === "directory"){
      const folder = result[node.name] = {};
      for(const sub of node.children)
           copyNode(sub, folder);

  } else {
      result[node.name] = node.path;
  }
  return result;
}

This is a simple recursive approach, this is not tail call recursive as it is very difficult ( = not worth it ) to traverse a tree with only one tail call.

edited Jan 15, 2018 at 16:08

answered Jan 15, 2018 at 16:03

Jonas Wilms

139k20 gold badges164 silver badges164 bronze badges

Comments

Nina Scholz · Accepted Answer · 2018-01-15 16:45:19Z

You could take a recursive approach by chekcing the type.

For 'directory' take an object and iterate the children.

Otherwise assign the path to the key with the given name.

function fn(source, target) {
    if (source.type === 'directory') {
        target[source.name] = {};
        (source.children || []).forEach(o => fn(o, target[source.name]));
    } else {
        target[source.name] = source.path;
    }
}

var source = { path: "photos", name: "photos", size: 600, type: "directory", children: [{ path: "photos/summer", name: "summer", size: 400, type: "directory", children: [{ path: "photos/summer/june", name: "june", size: 400, type: "directory", children: [{ path: "photos/summer/june/windsurf.jpg", name: "windsurf.jpg", size: 400, type: "file", extension: ".jpg" }] }] }, { path: "photos/winter", name: "winter", size: 200, type: "directory", children: [{ path: "photos/winter/january", name: "january", size: 200, type: "directory", children: [{ path: "photos/winter/january/ski.png", name: "ski.png", size: 100, type: "file", extension: ".png" }, { path: "photos/winter/january/snowboard.jpg", name: "snowboard.jpg", size: 100, type: "file", extension: ".jpg" }] }] }] },
    target = {};

fn(source, target);
    
console.log(target);

.as-console-wrapper { max-height: 100% !important; top: 0; }

Collectives™ on Stack Overflow

Tail recursive JSON constructor

3 Answers 3

2 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related