Tree queries

This chapter discusses techniques for processing queries on subtrees and paths of a rooted tree. For example, such queries are:

• what is the $k$th ancestor of a node?
• what is the sum of values in the subtree of a node?
• what is the sum of values on a path between two nodes?
• what is the lowest common ancestor of two nodes?