Tree traversal with conditional summing values from nodes

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).

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. It is possible to have sums for all nodes settled after one traversal?

Edit: There are no special relationships between nodes and also tree doesnt have any special properties. Tree is not binary tree as each node can have <0,Integer.MAX_VALUE> children.

To more describe my naive 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).

Answer 1

This algorithm is simple conceptually, but the implementation is a bit much so I'll try to present it in a couple steps. First, an example.

---

Linked List Example

Consider the following linked list where rank and value are equivalent: $A = [1, 3, 5, 6, 4, 2, 0]$

We will create auxiliary array $S$ where $S[i]$ is the sum of the subtree (sub-linked list) rooted at node $i$. This will basically be a suffix sum array for our purposes. This takes $O(n)$ time to create and it would be: $S = [21, 20, 17, 12, 6, 2, 0]$.

We will now process the nodes in order, adding them to a stack $T$. We have one rule before adding a node, if the node value on the top of the stack is greater than the node we're adding, then we must pop it from the top of the stack. This will ensure that when we pop a node off the stack, the current node we're at will be the first node lesser than it. Let's say we're popping node $i$ and we're currently at node $j$, then we have the function we're interested in is simply $f(i) = S[i] - S[j]$. Let's run through this with our example:

Let A = [ 1,  3,  5,  6, 4, 2, 0]
Let S = [21, 20, 17, 12, 6, 2, 0] be the suffix sum array of A
Let T be the increasing order stack, initially empty.

1) T = []
2) T = [1]
3) T = [1, 3]
4) T = [1, 3, 5]
5) T = [1, 3, 5, 6]
6) T = [1, 3, 4] and set f(6) = 12 - 6 = 6, set f(5) = 17 - 6 = 11
7) T = [1, 2]    and set f(4) =  6 - 2 = 4, set f(3) = 20 - 2 = 18
8) T = [0]       and set f(2) =  2 - 0 = 2, set f(1) = 21 - 0 = 21
9) T = []        and set f(0) = 0

We can take $f$ to be our final answer array where $f = [21, 18, 11, 6, 4, 2, 0]$.

---

Problem with applying this to a Tree

You may notice a problem with applying this to a tree. We are destroying the information of $T$ when we finally get to a leaf node. So to remedy this, we will have to rebuild it in a way as we come back up the recursion stack. For this we will need to keep track of a few more things. First, we will need to know the depth at which a node resides. This is easy to calculate in a single traversal of the tree. Next, we will need to know the depth at which a node was removed from $T$. This is also easy to keep track of during the recursion. So let's move to the next section of the algorithm itself.

---

The Algorithm Approach

Let's define some things we need. I'll simply add them as pointers on the node itself and assume that our stack $T$ holds a reference to the nodes. For a node $V$ let the node have the following properties:

• v.rank - rank of node $v$. (given)
• v.value - value of node $v$. (given)
• v.sum - the sum of the values of nodes in the subtree rooted at $v$ (precomputed).
• v.depth - the depth of node $v$ where the root is at depth 0. (precomputed)
• v.removal - the depth we are at when we remove node $v$ from $T$. This may be overwritten multiple times throughout the algorithm if $v$ has multiple children.
• v.f - the function we're interested in computing (based on the definition in the question). Initially set v.f = v.sum, and we will subtract away subtrees where necessary.

For the sake of dealing with base cases, I will assume w.l.o.g. that leaf nodes will have a dummy node attached to them as a child with value 0 and rank less than that of all nodes in the tree.

So we have our stack $T$, we will also have another stack $R$ which will keep track of the order of the nodes we've removed from $T$. This will be necessary to rebuild $T$ on our way back up from recursion. Assume $T$ and $R$ are global variables.

def visit(v, d): 
  // Where v is the node we're visiting, and d is the depth we're at.

  // Before recursion
  while top(T).rank > v.rank:
    u = pop(T)
    u.removal = d     // set depth of removal
    u.f = u.f - v.sum // remove sum of subtree rooted at v because it's lesser
    push(R, u)        // push it onto our removal stack R

  if v is not a dummy node:
    push(T, v)
    for each child u of v:
      visit(u, d + 1)

  // Build back up T, we use d - 1 because we're building it back up
  //   so that it is fixed for the level above (when recursion returns)
  while top(T).depth > d - 1:
    u = pop(T)        // we must remove nodes that are depth below our current

  while top(R).depth <= d - 1 and top(R).removal > d - 1:
    u = pop(R)
    push(T, u)

---

Example

Consider this tree (assume rank = value):

Let's work through the first few steps of this example explicitly:

• d = 0 | v = 2 | T = [2] | R = [] recurse on 4
• d = 1 | v = 4 | T = [2, 4] | R = [] recurse on 5
• d = 2 | v = 5 | T = [2, 4, 5] | R = [] recurse on 8
• d = 3 | v = 8 | T = [2, 4, 5, 8] | R = [] recurse on 7
• d = 4 | v = 7 | T = [2, 4, 5, 7] | R = [8] recurse on 0
  • set 8.f = 15 - 7 = 8 and 8.removal = 4
• d = 5 | v = 0 | T = [] | R = [8, 7, 5, 4, 2]
  • set 7.f = 7 - 0 = 7 and 7.removal = 5
  • set 5.f = 24 - 0 = 24 and 5.removal = 5
  • set 4.f = 53 - 0 = 53 and 4.removal = 5
  • set 2.f = 55 - 0 = 55 and 2.removal = 5
  • build T back up and return
• d = 4 | v = 7 | T = [2, 4, 5, 7] | R = [8]
  • build T back up and return
• d = 3 | v = 8 | T = [2, 4, 5, 8] | R = []
  • build T back up and return
• d = 2 | v = 5 | T = [2, 4, 5] | R = [] recurse on 3
• d = 3 | v = 3 | T = [2, 3] | R = [5, 4] recurse on 1
  • set 5.f = 24 - 4 = 20 and 5.removal = 3
  • set 4.f = 53 - 4 = 49 and 4.removal = 3
• d = 4 | v = 1 | T = [1] | R = [5, 4, 3, 2] recurse on 0
  • set 5.f = 24 - 4 = 20 and 5.removal = 3
  • set 4.f = 53 - 4 = 49 and 4.removal = 3
• ...

I will not continue the rest cause it will take a while, but you can see at this point all nodes in the subtree rooted at 5 have been completely evaluated.

---

Analysis

This is where I'm having a bit of trouble. It is technically one traversal of the tree, but I am not sure if this is $O(n + m)$. There would need to be some argument about how many times a node can be pushed and popped onto $T$ and $R$.

Consider a path $p$ from root to leaf. Every node on this path will be popped and pushed from $T$ and $R$ a constant number of times (similar argument as the linked list). Every time a node $v$ forks into $k$ children, this will increase the number of times nodes on the path from root to $v$ will be pushed and popped by a factor of $k$. When we reach the leaf node, $T$ will be empty and $R$ will be full.

You can upper bound this by the following formula. Let $k$ be the total number of leaf nodes, let $d$ be the maximum depth of the tree. Then the runtime is $O(kd)$.

To put this into perspective, for a binary tree of depth $\log n$ and $n/2$ leaf nodes, this runs in $O(n \log n)$.