Easier to read solution to 10.9?

#1

Hi
Would it not be easier to understand if one solves the non recursive IOT with parents pointers in this way:

n = FindMinimum(root)
print n
while (s=FindSuccessor(n))
    print s

where FindSuccessor(node*) is the solution to 10.11. Not that the proposed solution isn’t interesting, but it is not the easiest algorithm to read through, also it would motivate the reuse of 10.11.

0 Likes
#2

Hey zebullon,

Many thanks for your idea as it is a very good way of solving problem by using reduction. By understanding that inorder traversal actually starting from the leftmost element in a binary tree (i.e., FindMinimum(root) in your code), and keep calling successor actually nicely solves this problem for sure.

Thanks for proving that, and we will think about how to add those into the next version of EPI by either mentioning this or providing this as a variant.

Keep up the good work, zebullon!

0 Likes