It seems that in a full AVL tree, the left edge is always the minimum-cost path. For example, take the following full AVL tree:
The min-cost path would be 8-6-5
. However this is not the case with other AVL trees. Take the previous tree with an additional 4
inserted:
Here the min-cost path would be 8-6-7
rather than 8-6-5-4
.
What is the most efficient algorithm to find the min-cost path in any AVL tree? Given the characteristics of AVL trees, is this algorithm faster than it would be for a standard BST?