Computing parent nodes in threaded binary trees (Q1090107)

We give three algorithms for computing the parent of a node in a threaded binary tree, and calculate the average case complexity of each. By comparing these to the unit cost of obtaining the parent of a node with an explicit parent-pointer field, it is possible to balance runtime and storage cost with respect to the task of finding parent nodes in binary trees. The results obtained shows that, although the worst case complexity for an n-node tree is obviously O(n) for all three algorithms, the average case complexity for two input distributions is asymptotic (from below) to either 3 or 2.