Time Complexity of Tree DP

Each node is visited exactly once during DFS. At each node, you loop through its children to aggregate values. Total work: $O(n)$ where $n$ is the number of nodes. Each edge is traversed twice (down and back up), giving $O(n)$ edge traversals.

Tree DP is fast. No repeated subproblems like in grid DP. The tree structure guarantees linear time. This makes tree DP practical even for large trees with millions of nodes.

Space complexity is $O(n)$ for the data structures used.