Javascript - Traverse A Tree To Generate The Sequence Of The Nodes

Question

I have found few SO questions relevant to this but none of them were based on the exact problem I am trying to solve.

Basically, I am working on a tree structure and every node is assigned an id.

The objective is to generate a sequence string that will provide a path to traverse the entire tree sequentially.

As an example the output of following diagram should be 123242523637321

As you can see, the tree starts at node 1 and then goes to node 2.

Node 2 is connected to 3 other nodes viz. node 3, node 4 & node 5.

Following the sequence, the next node is 3.

To go to the next node i.e. node 4, we will have to go back to node 2 and then go to node 4, so the string becomes 12324

Once we get the last node i.e. node 7, we will go back to the first node and hence the string ends with a substring 7321

I am trying to construct a logic that would generate the string from a given tree structure.

Sample tree structure for above diagram is -

const sequenceObj = {
    1: {
        id: "Point_1cec2262-20f8-4985-adcb-b6d95a618d22",
        connectedNodes: ["2"]
    },
    2: {
        id: "Point_02bdae16-1cdb-48e1-a601-7b1e526eedb8",
        connectedNodes: ["1", "3", "4", "5"]
    },
    3: {
        id: "Point_55a68ac0-17ef-48a2-bf9f-c70004a27d99",
        connectedNodes: ["2", "6", "7"]
    },
    4: {
        id: "Point_8760427c-98bb-4e3e-85dd-59cba3b31c6f",
        connectedNodes: ["2"]
    },
    5: {
        id: "Point_79a7bcec-d110-43dc-b9ac-1552538bc1a5",
        connectedNodes: ["2"]
    },
    6: {
        id: "Point_37550cf0-4bd5-48b2-b32f-9018bd55c05f",
        connectedNodes: ["3"]
    },
    7: {
        id: "Point_2de67998-9e1f-4b06-af18-77d558d68254",
        connectedNodes: ["3"]
    }
};

As you can see, every node has a property called connectedNodes which helps us traverse the tree.

EDIT - As pointed out in comments, the property connectedNodes (which was previously called children) stores the ids of connected nodes. The provided object does not represent the tree, we only need to use this object to traverse from start to end i.e. from id 1 to 7 in this example.

Let me know if I have missed something or if more information is required.

Thanks!

Your input appears incorrect. `2: { children: [ "1", "3", "4", "5" ] }`, why does `1` appear as a child of `2`? Why does `2` appears as a child of `4`, `5`? Why is `3` a child of `6` and `7`? This doesn't make sense — Mulan, Mar 14 '21 at 20:39
@Thankyou Apologies for using incorrect naming conventions. The property children is storing ids of all the connected nodes (which is what I am getting as an API response. I think calling it `connectedNodes` would make more sense. I will update the question. — planet_hunter, Mar 15 '21 at 09:36

score 1 · Answer 1 · answered Mar 14 '21 at 20:52

Your input is written in a that nodes list their parents as children. We fix that first -

const node = (id, ...children) =>
  ({ constructor: node, id, children })

const tree =
  node(1, node(2, node(3, node(7), node(6)), node(4), node(5)))

Now we can write your traverse -

function* traverse(t)
{ switch (t?.constructor)
  { case node:
      yield t.id
      for (const c of t.children)
      { yield *traverse(c)
        yield t.id
      }
  }
}

for (const v of traverse(tree))
  console.log(v)

Or we can collect them all in one string

console.log(Array.from(traverse(tree)).join(""))

Expand the snippet below to verify the results in your own browser -

const node = (id, ...children) =>
  ({ constructor: node, id, children })

function* traverse(t)
{ switch (t?.constructor)
  { case node:
      yield t.id
      for (const c of t.children)
      { yield *traverse(c)
        yield t.id
      }
  }
}

const tree =
  node(1, node(2, node(3, node(7), node(6)), node(4), node(5)))

console.log(Array.from(traverse(tree)).join(""))

1237363242521

score 0 · Answer 2 · answered Mar 14 '21 at 20:45

You could take seen nodes out of the children array and get the nodes of unseen keys.

const
    getSequence = (key, seen = {}) => {
        seen[key] = true;

        const unseen = sequenceObj[key]
                .children
                .filter(k => !seen[k]);

        return unseen.length
            ? `${key}${unseen.flatMap(k => getSequence(k, seen)).join(key)}${key}`
            : key;
    },
    sequenceObj = { 1: { id: "Point_1cec2262-20f8-4985-adcb-b6d95a618d22", children: ["2"] }, 2: { id: "Point_02bdae16-1cdb-48e1-a601-7b1e526eedb8", children: ["1", "3", "4", "5"] }, 3: { id: "Point_55a68ac0-17ef-48a2-bf9f-c70004a27d99", children: ["2", "6", "7"] }, 4: { id: "Point_8760427c-98bb-4e3e-85dd-59cba3b31c6f", children: ["2"] }, 5: { id: "Point_79a7bcec-d110-43dc-b9ac-1552538bc1a5", children: ["2"] }, 6: { id: "Point_37550cf0-4bd5-48b2-b32f-9018bd55c05f", children: ["3"] }, 7: { id: "Point_2de67998-9e1f-4b06-af18-77d558d68254", children: ["3"] } };

console.log(getSequence('1'));

Javascript - Traverse A Tree To Generate The Sequence Of The Nodes

2 Answers2