0

I have an n-ary tree structure which has a functionality such that any node in the tree can be referenced. This means the referencing node will take it's value from the referenced node.

Rule number 1: The value of a node is computed from its children A reference node saves you from creating a structure you have already created in the tree by letting you set a reference node and just copy its value to your preferred place in the tree. Since you have just inserted a value somewhere in this tree now it should be cascaded upwards because Rule number 1 must be satisfied.

Rule number 2: Child nodes which are used to compute value of a parent node are always leaf nodes.

Rule number 3: Cyclic references are not allowed.

Rule number 4: Root node cannot be referenced.

Tree nodes have a value which are added and that is the value of their parent node. e.g. if two child nodes have a value of 10, then their parent node's value will be 20.

Since the tree is initialized without taking reference nodes into account, references nodes should be found via a new method.

The problem is after finding the reference node, its value should be cascaded up to the root of the tree.

How can I implement this behaviour? I can find a reference node in the current tree but cascading it upwards is the issue.

Visual example:

enter image description here

public class TreeNode {
    private Long id;
    private TreeNode parent;
    private List<TreeNode> children = new ArrayList<TreeNode>();
    private TreeNode referenceNode;
    private BigDecimal value = BigDecimal.ZERO;
}
public class TreeNodeService {
    public List<TreeNode> getTreeNodes() {
        List<TreeNode> treeData = new ArrayList<TreeNode>(); // assume treeData is filled by database call
        if (treeData.size() > 0) {
            findReferenceNode(treeData, treeData);
        }
        return treeData;
    }
    private void findReferenceNode(List<TreeNode> allNodes,
                                   List<TreeNode> currentNodeHolder) {
        if (currentNodeHolder.size() > 0) {
            TreeNode currentNode = currentNodeHolder.get(0);
            for (TreeNode childNode : currentNode.getChildren()) {
                if (childNode.getReferenceNode() != null) {
                    setReferenceNodeValue(childNode.getReferenceNode().getId(),
                                          allNodes,
                                          childNode,
                                          currentNode);
                }
                findReferenceNode(allNodes,
                                  Arrays.asList(childNode));
            }
        }
    }
    private void setReferenceNodeValue(Long referenceId,
                                       List<TreeNode> allNodes,
                                       TreeNode childNode,
                                       TreeNode parentNode) {
        if (allNodes.size() > 0 && referenceId != null) {
            TreeNode rootNode = allNodes.get(0);
            for (TreeNode innerChild : rootNode.getChildren()) {
                // If there is a match, then innerChild is our original node which
                // is being referenced by childNode
                if (innerChild.getId().equals(referenceId)) {
                    // Copy original node value and set reference node value with it
                    childNode.setValue(innerChild.getValue());
                    // Parent of this reference node might have a non-zero value already set
                    BigDecimal startValue = parentNode.getValue();
                    updateParentNodeValue(parentNode,
                                          startValue,
                                          childNode.getValue());
                } else {
                    setReferenceNodeValue(referenceId,
                                          Arrays.asList(innerChild),
                                          childNode,
                                          parentNode);
                }
            }
        }
    }
    private void updateParentNodeValue(TreeNode parentNode,
                                       BigDecimal startValue,
                                       BigDecimal valueToAdd) {
        BigDecimal finalValue = startValue.add(valueToAdd);
        parentNode.setValue(finalValue);
    }
}
ardatosun
  • 457
  • 4
  • 22
  • 1
    I dont get your requirements. Either the "value" of a node is computed from its children, or it is not. But it sounds like you want to have both ways. If that is the case, then maybe you should really distinguish between these two **different** kinds of values. – GhostCat Aug 31 '20 at 08:22
  • `Rule number 1: The value of a node is computed from its children` A reference node saves you from creating a structure you have already created in the tree by letting you set a reference node and just copy its value to your preferred place in the tree. Since you have just inserted a value somewhere in this tree now it should be cascaded upwards because Rule number 1 must be satisfied. – ardatosun Aug 31 '20 at 08:25
  • I don't get it either `any node in the tree can be referenced` - no idea what that means...`referencing node will take it's value from the referenced node` - what? `tree is initialized without taking reference nodes into account` - how so? – dbl Aug 31 '20 at 08:27
  • Please update your question. All information should sit in the question, instead of various comments. – GhostCat Aug 31 '20 at 08:27
  • Are leaf nodes (which have a value of their own used to compute the parent nodes) different in some way from the parent nodes? In other words, will a leaf node always be a leaf node? – NomadMaker Aug 31 '20 at 08:27
  • Either way, you should maintain actual value instead of calculating it each time. Update values for each insert/delete operations. – dbl Aug 31 '20 at 08:31
  • Please see the updated OP. – ardatosun Aug 31 '20 at 08:40
  • I am confused even more now :) How is that a tree xD [NOT A TREE](https://stackoverflow.com/questions/37907339/how-to-detect-circular-reference-in-a-tree) – dbl Aug 31 '20 at 08:50
  • There are no cyclic dependencies since only the value is copied not the whole node structure which means you can not go back and visit a node you have visited before while traversing the tree. – ardatosun Aug 31 '20 at 08:56
  • @ardatosun unless `AAA` references `B` :) – dbl Aug 31 '20 at 08:58
  • @dbl good point. Updated OP. I missed adding that rule. There cannot be cyclic relations such as the one you suggested. – ardatosun Aug 31 '20 at 09:12
  • So you claim that the `value` is set for leaves only? Why do you need to calculate `value`s if they are already set? If no values are set then the weight of each node will be `0`. If there are values set for leaves only, no matter witch of the nodes is your target, you will have to recalculate wights for all nodes! If each node has a `value` then why not recalculating the tree for each insert/update/delete operation? – dbl Aug 31 '20 at 09:33
  • Let us [continue this discussion in chat](https://chat.stackoverflow.com/rooms/220727/discussion-between-ardatosun-and-dbl). – ardatosun Aug 31 '20 at 09:36
  • The clause _'any node in the tree can be referenced'_ contradicts the rule _'The value of a node is computed from its children'_ – if you reference a root node, its value will depend (directly or indirectly) on the value of itself. Hence it will be undefined. So, at least the root node _must not_ be referenced. – CiaPan Sep 02 '20 at 16:56
  • Yes that is correct, root node can not be referenced. – ardatosun Sep 03 '20 at 17:24

0 Answers0