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!

Answer 1

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

Answer 2

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)

1
2
3
7
3
6
3
2
4
2
5
2
1

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