How to walkthrough a tree and calculate value on path?

Community Support
1

Hi there,

Input:

 

tree:(parent:AAABBEE;child:BCDEFGH;data:(1;2;3;4;5;6;7));

 

How to get output as in this chart?

Thank you.

 

2

Thanks for posting ! Looking forward to seeing what the community’s approach to this is.

3

This gets it done while remaining somewhat readable:

child:select (child,'data) by parent from tree; res:(); a:(start:key[child];end:key[child];val:1); while[count a; res,:select from a where not end in key child; b:ungroup update nxt:child end from (delete from a where not end in key child); a:select start, end:nxt[;0], val*nxt[;1] from b; ];

The answer is given by

q)startend xasc res start end val ------------- A C 2 A D 3 A F 5 A G 24 A H 28 B F 5 B G 24 B H 28 E G 6 E H 7

4

Try to traverse through Dictionary

tree:(parent:AAABBEE;child:BCDEFGH;data:(1;2;3;4;5;6;7)); tree:(parent:AAABBEE;child:BCDEFGH;data:(1;2;3;4;5;6;7)); traverse_dict:exec child!parent from tree; calc:ADCBFEGH!1 3 2 1 5 4 6 7; traverse_func:{[st;end;dict;calc] prd calc except[(dict) end;(dict) st] }[;;traverse_dict;calc]; outputTree:( parent:AAAAABBBEE;child:CDFGHFGHGH); // output update val:traverse_func’[parent;child] from outputTree

 

5

Really like this solution, haven’t seen a scan indexing before. Just wanted to add to it so the user doesn’t have to define  calc and  outputTree :

tree:(parent:AAABBEE;child:BCDEFGH;data:(1;2;3;4;5;6;7)); traverse_dict:exec child!parent from tree; root:A; // value pairing appending root node with 1 factor calc:(root, exec child from tree)!1,exec data from tree; // calc:ADCBFEGH!1 3 2 1 5 4 6 7; traverse_func:{[st;end;dict;calc] prd calc except[(dict\) end;(dict\) st] }[;;traverse_dict;calc]; outputTree:exec child by parent from tree; outputTree:key[outputTree]!raze each (value outputTree),' outputTree value outputTree; outputTree:(key outputTree)!except[;key outputTree]each distinct each (raze/) each (outputTree\)each value outputTree; p:raze (count each value outputTree)#'key[outputTree]; c:raze value outputTree; outputTree:([] parent:p;child:c); // outputTree:([] parent:AAAAABBBEE;child:CDFGHFGHG`H); // output update val:traverse_func’[parent;child] from outputTree

There’s probably a more concise way to do the above so keen to see any further improvements.

6

This is my solution

tree:(parent:AAABBEE;child:BCDEFGH;data:1 2 3 4 5 6 7); getVal:{?[tree;((=;parent;enlist x);(=;child;enlist y));();data]} checkParent:{first ?[`tree;enlist (=;`child;enlist x);();`parent]} getPathVal:{[x;y] $[x~checkParent[y];getVal[x;y];getVal[checkParent[y];y]*.z.s[x;checkParent[y]]]}

 

7

Another method:

tree:(parent:AAABBEE;child:BCDEFGH;data:1 2 3 4 5 6 7); dl:-1_ s:{x iasc 2#/:x} // sort lr:{flip dl(x)y} // leaf to root lar:{(sum[n]-2)dl\x where n:not null x} // leaf to all roots gw:{((last;first)@:y),prd x dl flip 1 next\y} // get weights walk:{ d:exec child!parent from x; w:exec(child,'parent)!data from x; s gw[w;]each raze lar each lrd;xchildparent } walk tree A C 2 A D 3 A F 5 A G 24 A H 28 B F 5 B G 24 B H 28 E G 6 E H 7

8

It’s faster to keep track of the running products at each step:

tree:(parent:AAABBEE;child:BCDEFGH;data:1 2 3 4 5 6 7); sort:{x iasc 2#/:x:x@'(-1+count each x),:1 0} step:{.[z;(::;0);*;]y -2#/:z:(z,'x l)where(l:last each z)in key x} walk2:{ d:exec child!parent from x; w:exec(child,‘parent)!data from x; sort raze 1_(step[d;w;])1,’(except/)xchildparent } walk2 tree A C 2 A D 3 A F 5 A G 24 A H 28 B F 5 B G 24 B H 28 E G 6 E H 7 q)\ts do[50000;walk tree] 1930 3584j q)\ts do[50000;walk2 tree] 1259 3440j