can you gives us example data for treeStructure.data
?
[
{
_id: number,
parent: number,
value: string
}
]
to get as close as I could to your code I ended up with the following:
const myDataStructure = {
data: [
{
_id: 0,
parent: 0,
children: [10, 12],
value: null
},
{
_id: 10,
parent: 0,
children: [22, 23],
value: "Metal"
},
{
_id: 22,
parent: 10,
children: [22],
value: "Aluminum"
},
{
_id: 30,
parent: 22,
children: [0],
value: null
},
{
_id: 12,
parent: 0,
children: [24],
value: "Plastic"
},
{
_id: 23,
parent: 10,
children: [0],
value: "Iron"
},
{
_id: 24,
parent: 12,
children: [33, 38],
value: "Soda"
},
{
_id: 33,
parent: 24,
children: [40],
value: "MtDew"
},
{
_id: 38,
parent: 24,
children: [0],
value: "Pepsi"
},
{
_id: 40,
parent: 33,
children: [40],
value: "Diet MtDew"
},
{
_id: 50,
parent: 40,
children: [0],
value: "Diet Double Dew"
},
] //end data prop
} //end obj
const data = myDataStructure.data;
function buildTree(node, nodeArray){
if(node.parent) {
const parentNode = data.find(item => item._id === node.parent);
//to fix needing to use .reverse() switch the following 2 lines so they're in this order:
buildTree(parentNode, nodeArray);
nodeArray.push(node.value);
}
else{
nodeArray.push(node.value);
}
}
function buildTree2({parent, value}, nodeArray){
if(parent) {
const parentNode = data.find(({_id}) => _id === parent);
buildTree2(parentNode, nodeArray);
}
nodeArray.push(value);
}
const treeArray = [];
data.forEach((node) => {
const nodeArray = [];
buildTree2(node, nodeArray);
treeArray.push(nodeArray);
});
return treeArray;
I did go ahead and make buildTree() so you don't need to use .reverse() later on. I also included buildTree2() which just has a small improvement. the addition of the children
property for each leaf/node will let you use in-order, pre-order and post-order seach strategies. i also used _id's starting with the magnitude (the number in parentheses bellow)... if you really wanted to you can combine this w the use of children
re-order/build your tree by id changing ur basic Trie(tree) into an AVL Trie (self balancing) w just a couple rebalancing/rotation functions. if you have large datasets the normal tree you have can get way off balance leading to some searches always taking forever. to be considered balanced the largest difference in magnitude of any node needs to can only be +/- 1. bellow u can see Diet Double Dew has a mag of 5 and Pepsi of 3, making the Soda node unbalanced
the only problem here is that this code works =/. the only difference between ours should be the data structure, but I can't help too much there without seeing the type/structure of the node
variable or of treeStructure.data
. heres the output from above though:
sorry if the tree rant is too much... lol i REALLY like data structures and the AVL Tree is actually my favorite . btw if anybody can tell me why some places have them spelled Trie and others Tree I'd be super happy, it always bothers me and I've just assumed it was some old-timey spelling or weird British spelling (color doesn't have a 'u' in it!!!) but I'm sure I'm wrong... probably... idk but it's weird to see