Skip to content

Instantly share code, notes, and snippets.

@JWally
Last active September 8, 2022 12:13
Show Gist options
  • Save JWally/7386567 to your computer and use it in GitHub Desktop.
Save JWally/7386567 to your computer and use it in GitHub Desktop.
Javascript Algorithm to build an org chart from an array of related objects
var ary = [
{id: "a", parent: 0},
{id: "b", parent: "a"},
{id: "c", parent: "b"},
{id: "d", parent: "c"},
{id: "e", parent: "d"},
{id: "f", parent: "e"},
{id: "g", parent: "f"},
{id: "h", parent: "g"},
{id: "i", parent: "h"},
{id: "1", parent: "Dan Band"},
{id: "2", parent: "1"},
{id: "3", parent: "2"},
{id: "4", parent: "3"},
{id: "5", parent: "4"},
{id: "6", parent: "5"},
{id: "7", parent: "6"},
{id: "8", parent: "7"},
{id: "9", parent: "8"},
{id: "c1", parent: "c"},
{id: "c2", parent: "c1"},
{id: "c3", parent: "c2"},
{id: "c4", parent: "c3"},
{id: "c5", parent: "c4"},
{id: "c6", parent: "c5"},
{id: "c7", parent: "c6"},
{id: "c8", parent: "c7"},
{id: "c9", parent: "c8"}
];
var monkey = {
// The Tree
"tree": {
"children": []
},
// Main function to build the tree
"build_tree": function (ary, id_field, parent_field) {
this.tree[id_field] = "root";
this._build(ary, id_field, parent_field);
return true;
},
// Function to push children in arrays
"_build": function (ary, id_field, parent_field) {
var x,
i;
this.map = {};
// Step 1. Create a "hash map" of all objects
for (i = 0; i < ary.length; i++) {
this.map[ary[i][id_field]] = ary[i];
}
// Step 2. Iterate over the "hash map"
for (x in this.map) {
// 2a. Does the current object have a parent on the map?
if (this.map[this.map[x][parent_field]]) {
// This object has a parent. Hop in their kiddie pool (children array)!
if (this.map[this.map[x][parent_field]].children) {
this.map[this.map[x][parent_field]].children.push(this.map[x]);
} else {
this.map[this.map[x][parent_field]].children = [this.map[x]];
}
} else {
// Object has no parent. It's a Node. Add to root's children.
this.tree.children.push(this.map[x]);
}
}
},
// Find a node by id in the map, and apply a function to it,
// and all of its ancestors
"_back_trace": function (id, parent_field, fx) {
if (this.map[this.map[id][parent_field]]) {
// Apply the function
fx(this.map[id]);
this._back_trace(this.map[id][parent_field], parent_field, fx);
}
}
};
monkey.build_tree(ary, "id", "parent");
console.log(JSON.stringify(monkey.tree));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment