Efficiently finding the min-cost path of an AVL tree

Question

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?

Answer 1

Searching in an AVL tree is anyways only at most O(log n) (see on @Wikipedia: https://en.wikipedia.org/wiki/AVL_tree?wprov=sfta1). If you do not care about the higher cost of rebalancing AVL tree instead of BSTree, this tree will have even the advantage of always maintaining the AVL-min-cost path on the left edge. Search the left edge has also O(log n) so no cheaper than other trees. Balancing a tree is only nesessary if building a tree can cause massive imbalance, only than AVL has a marginal advantage above BST.

To your counter example on AVL tree with a not-left-edge min-cost: This is to my quick grasp the furthest imbalance one can find before need of rebalancing of AVL is needed. Hence no need to worry about finding the minimum cost path in AVL tree may be more difficult due to tree depth. So searching the minimum path within the left and not totally left path is O(log n +1) equaling O(log n). So it is basically not harder to find the actual minimum path than finding the obvious left edge.