Implement a Binary Search Tree, but include a pre$-$order, in$-$order, and post$-$order search. The search functions should take a root and an index. For Kudo points, please include an AVL tree that can be used to reorder the height of the BST$.$ Do this first in P$-$code, then write it in Python. This function should work with any language.