Optimal solution for tree traversal and summing node values on condition

Question

Hi all i have algorithmic problem and i struggle with finding optimal solution. I have tree which i want to traverse. Nodes of the tree consist of value and a rank of node (value as well as rank can be random number).

What i want to do is traverse tree and for each node i want to sum values from all descendant nodes except descendants with lower rank and all nodes under them (irrespective of rank). Tree does not have any special properties as every node can have <0, Integer.MAX_VALUE> of children. There are no rules applied on relations between parent and children regarding rank or value.

My naive solution is to recursively traverse subtree for each node and stop recursion as soon as i find node with lower rank, summing values on my way back to root of subtree. However this feels to me like suboptimal solution (in worst case - that is each node has only one descendant - its basically linked list and ranks are sorted ascending to the root this solution would be O(n^2)).

It is possible to have sums for all nodes settled after one traversal?

Edit: Solution, slightly better as my naive approach could be for every node visited propagate its value recursively back to the root while keeping minimum rank of visited nodes (during back to root traversal). Then adding value only to nodes that have lower than minimal rank.

Answer 1

Edit from my phone: since we only ever inspect the value of tree roots, we can use a disjoint sets structure with path compression only instead of a dynamic tree. Don't bother updating non-roots.

Here's an O(n log n)-time algorithm with dynamic trees. (I know. They're a pain to implement. I try not to include them in answers.)

Sort the nodes from greatest to least rank and initialize a totally disconnected dynamic tree with their values. For each node in order, issue dynamic tree operations to

1. Report its current value (O(log n) amortized, output this value eventually), and
2. If it's not the root, add its value to each of its ancestors' values (O(log n) amortized) and then link it to its parent (also O(log n) amortized).

The effect of Step 2 is that each node's dynamic value is the sum of its descendants' (relative to the present tree) original values.

Answer 2

Edit Not correct answer, does not solve the problem asked by the OP (cf comment)
Old answer (before edit) You can see that this problem (like most problem on trees) can be solved with a recursive approach. That is because the sum value of a node depends only on the sum values and respective ranks of its children.

Here is a pseudo-code describing a solution.

get_sum(my_node, result_arr):
    my_sum = 0
    for child in my_node.children():
        get_sum(child, result_arr)        // we compute the sum value of the children
        if rank(child) >= rank(my_node):  // if child node is big enough add its sum
            my_sum += result_arr[child]
     result_arr[my_node] = my_sum         // store the result somewhere

This is a BFS based algorithm, which should run in O(n) with n the number of nodes in your tree. To get the values for all the nodes, call this recursive function on the root node of your tree.

Answer 3

I suggest you a postfixed DFS. For every node, keep the reference of its predecessor.

• the sum_by_rank for a leaf is an empty dict;
• the sum_by_rank for any node is the dict ranks of all subnodes -> values of all subodes. If two or more subnodes have the same rank, just add their values.

The postfixed DFS allows you to compute the sums from bottom to up.

Here's some Python 3.7 program to play with (the code is probably not optimized):

from dataclasses import dataclass
from typing import List, Dict

@dataclass
class Node:
    value: int
    rank: int
    sum_by_rank: Dict[int, int]
    children: List[object]

tree = Node(5, 0, {}, [
        Node(4,2, {}, [Node(3,1, {}, [])]),
        Node(7,2, {}, [Node(11,1, {}, [Node(7,8, {}, [])])]),
        Node(8,4, {}, [Node(3,3, {}, []), Node(9,5, {}, []), Node(4,2, {}, [])]),
    ])

def dfs(node, previous=None):
    for child in node.children:
        dfs(child, node)
        node.sum_by_rank[child.rank] = node.sum_by_rank.get(child.rank, 0) + child.value # add this children rank -> value
        # add the subtree rank -> value 
        for r,v in child.sum_by_rank.items():
            node.sum_by_rank[r] = node.sum_by_rank.get(r, 0)+v

dfs(tree)
print (tree)
# Node(value=5, rank=0, sum_by_rank={2: 15, 1: 14, 8: 7, 4: 8, 3: 3, 5: 9}, children=[Node(value=4, rank=2, sum_by_rank={1: 3}, children=[Node(value=3, rank=1, sum_by_rank={}, children=[])]), Node(value=7, rank=2, sum_by_rank={1: 11, 8: 7}, children=[Node(value=11, rank=1, sum_by_rank={8: 7}, children=[Node(value=7, rank=8, sum_by_rank={}, children=[])])]), Node(value=8, rank=4, sum_by_rank={3: 3, 5: 9, 2: 4}, children=[Node(value=3, rank=3, sum_by_rank={}, children=[]), Node(value=9, rank=5, sum_by_rank={}, children=[]), Node(value=4, rank=2, sum_by_rank={}, children=[])])])

Hence, to get the sum of a node, just add the values is associated with the ranks greater or equal to the node rank. In Python:

sum(value for rank, value in node.sum_by_rank.items() where rank >= node.rank)

Answer 4

Let a, b, c be nodes. Assume that a is an ancestor or b, and b is an ancestor of c.

Observe: if b.rank > c.rank and a.rank > b.rank then a.rank > c.rank. This leads us to the conclusion that the sum_by_rank of a is equal to the sum of sum_by_rank(b) + b.value for every b direct child of a, having a rank lower than a.

That suggests the following recursion:

ComputeRank(v)
    if v is null
       return

    let sum = 0
    foreach child in v.children
        ComputeRank(child)
        if child.rank <= v.rank 
            sum += child.sumByRank + child.value

    v.sumByRank = sum

By the end of the algorithm each node will have it's sumByRank as you required (if I understood correctly). Observe that for each node n in the input tree, the algorithm will visit n exactly once, and query it once again while visiting it's predecessor. This is a constant number of times, meaning the algorithm will take O(N) time.

Hope it helps :)