CODEWITHSUNDEEP
javascripttypescriptrecursiontree
tom
tom

Reputation: 2357

Create a tree data structure with the same shape as another

Let's say I have a typical tree data structure that looks like this:

[
  {
    att1: 'asdasd',
    att2: 42,
    att3: true,
    subs: [ ...other objects... ]
  },
  ...other objects...
]

It can have any shape and number of nodes, but every node has these three attributes (which have of course different values for each node).

Now, I'd like to create a new tree that would have the exact same hierarchy, but it should hold the data let's say in a format like this:

[
  {
    data: { att1: 'asdasd', att2: 42, att3: true },
    subs: [ ...other objects... ]
  },
  ...other objects...
]

( One way of implementing this would be to write a recursive function that visits every node of the original tree, creates the data attribute for each one, fills up its content by the three attributes att1, att2 and att3, then removes these attributes of the node. This way I would have this new tree. But I don't want to change the original tree, so this is not an option for me. I also don't want to clone the tree using JSON.parse(JSON.stringify()) or in some other way and then perform the same procedure described above for this new tree. )

Instead, I'm looking for a method to generate this new tree node by node, as I'm reading the original tree node by node.

A method I can already write that visits every node of the original tree:

public copyTree(originalTree: Array<object>): Array<object> {

  const newTree: Array<object> = [];

  function f(subtree: Array<object>): void {
    for (const node of subtree) {

      // Missing here: Somehow add the current node to newTree

      if (node['subs'].length > 0) f(node['subs']);
    }
  }
  f(originalTree);
  return newTree;

}

How could I complete this method (or you can show me a different implementation too) to generate the new tree?

Upvotes: 0

Views: 2213

Answers (3)

castletheperson
castletheperson

Reputation: 33496

You can do that using the Array.prototype.map function and recursion:

public copyTree(originalTree: Array<object>): Array<object> {
  return originalTree.map(({ subs, ...data }: any) => ({
    data,
    subs: this.copyTree(subs)
  }));
}

Upvotes: 2

casieber
casieber

Reputation: 7542

If you start by defining interfaces for your input and output shapes, you can use them and any resulting TypeScript errors to help guide you:

interface Attributes {
    att1: string;
    att2: number;
    att3: boolean;
}

type InputNode = Attributes & {
    subs: InputNode[];
}

interface OutputNode {
    data: Attributes;
    subs: OutputNode[];
}

Once we have those, we can set up our function definition as

function copyTree(originalTree: InputNode[]): OutputNode[] {

And then you can use rest/spread to help transfer everything around:

function copyTree(originalTree: InputNode[]): OutputNode[] {
    return originalTree.map(input => {
        const {
            subs,
            ...data
        } = input;

        return {
            subs: copyTree(subs),
            data,
        };
    });
}

Upvotes: 2

Oscar Paz
Oscar Paz

Reputation: 18302

Well, I'd do it using map and the spread/rest operators:

const array = [...];

const copy = array.map(item => {
    const {att1, att2, att3, ...rest} = item;
    return { data: {att1, att2, att3}, ...rest };
});

In this function, rest will hold all the properties in the object except att1, att2, att3. When creating the new object, adding ...rest adds the other properties to the resulting object, so, if you have:

{
    att1: '1',
    att2: '2',
    att3: '3',
    subs: [...],
    other: 'other'
}

you'd end with objects like this:

{
    data: {att1: '1', att2: '2', att3: '3'},
    subs: [...],
    other: 'other'
}

Upvotes: 1

Related Questions