Justify Table 7.1, summarizing the running time of the functions of a tree represented with a linked structure, by providing, for each function, a description of its implementation, and an analysis of its running time.

Data from in Table 7.1

Running times of the functions of an n-node linked tree structure. Let c_p  denote the number of children of a node p. The space usage is O(n).

Transcribed Image Text:

Operation isRoot, is External parent children (p) size, empty root Time 0(1) 0(1) O(Cp) 0(1) 0(1) positions O(n)