165. In a first-child/next-sibling tree, compute the sum of all elements, the number of siblings of a node, and the number of children of a node.
EasyTrees
Technical
Show model answer
Sum: `sum(node) = 0` for null, else `node.val + sum(node.firstChild) + sum(node.nextSibling)`, which visits every node once, O(n) time and O(depth) recursion (sibling chains add to the depth, so an iterative version with a stack can be safer).
Children of a node: start at `firstChild` and count along `nextSibling`, O(number of children). Siblings of a node: count the whole child list of its parent and subtract 1 for the node itself; if there is no parent pointer, counting only the siblings to its right needs nothing more than walking `nextSibling` from the node.