Assume the following notation/operations on AVL trees. An empty AVL tree is denoted E. A non-empty AVL tree T has three attributes:
• The key T.key is the root node’s key.
• The left child T.left is T’s left subtree, which is an AVL tree (possibly E).
• The right child T.right is T’s right subtree, which is an AVL tree (possibly E).
I'm trying to write an algorithm (pseudocode would do) Count(T, lo, hi) that counts and returns the number of nodes in an AVL tree with root T, where the key value is in the range lo ≤ key ≤ hi. I want it to have time complexity O(n) where n is the number of nodes in the AVL tree T. One idea I had was recursion but this didn't seem to have the required complexity. Any ideas?
You can add a global variable like counter, iterate the tree with Pre-order this has a cost of (n+e) and add 1 for each node.
You can add a counter too, and when add a new node inside the data structure, you can add 1, and if you remove a node you can subtract 1