Create a tree data structure with the same shape as another

Question

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?

castletheperson · Accepted Answer · 2018-06-16 21:59:33Z

2

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)
  }));
}

edited Jun 16, 2018 at 21:59

answered Jun 16, 2018 at 21:54

castletheperson

33.7k11 gold badges74 silver badges111 bronze badges

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

1 Comment

tom Over a year ago

I never have thought of using recursion this way inside a map(). I love this one probably the most.

casieber · Accepted Answer · 2018-06-16 21:56:44Z

2

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,
        };
    });
}

answered Jun 16, 2018 at 21:56

casieber

7,6222 gold badges23 silver badges35 bronze badges

1 Comment

tom Over a year ago

I really like this approach with the type alias and interface definitions and then letting typescript do the work. For my current task I find it a bit overkill however, but this example gave me some new aspects to consider for my other works, thank you!

Oscar Paz · Accepted Answer · 2018-06-16 21:48:09Z

1

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'
}

answered Jun 16, 2018 at 21:48

Oscar Paz

18.3k3 gold badges30 silver badges43 bronze badges

1 Comment

tom Over a year ago

Can it be that this one only works for one dimensional arrays and not for a tree structure I have, or do I overlook something?

Collectives™ on Stack Overflow

Create a tree data structure with the same shape as another

3 Answers 3

1 Comment

1 Comment

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related