Subtree Queries - Walkthrough

I'll walk you through a complete example. Tree structure: node $1$ (root) has children $2$ and $3$. Node $2$ has child $4$. Each node holds a value: $1 \to 4$, $2 \to 2$, $3 \to 5$, $4 \to 1$.

DFS visits nodes in order: $1 \to 2 \to 4 \to 3$. Entry times (when first visited): node $1$ gets $0$, node $2$ gets $1$, node $4$ gets $2$, node $3$ gets $3$. Exit times mark when you leave each subtree.

Flatten values by entry time into arr = [4, 2, 1, 5]. Node $2$'s subtree spans indices $[1, 3)$ in this array. Sum those positions: $2 + 1 = 3$. Update node $4$'s value to $10$ by changing arr[2]. Now node $2$'s subtree sums to $12$.