1. The problem statement, all variables and given/known data An avl tree typically balances with a balance factor of -1, 1, 0. What if the tree allows -2,-1,,0,1, 2 as a balance factor. Prove or disprove that the height of the tree is logarithmic to the number of nodes O(logn) 2. Relevant equations Normal balanced AVL tree everyone uses is h=O(logn) 3. The attempt at a solution I constructed several diagrams. Little hard to draw but i have root + 2 nodes going down a left path. log(3) = 1.584963 Actual height: 2 Another 3 nodes down left path, 1 down right path, 1 root log(5) = 2.32 Actual height: 3 Adding one more node down left side then balancing to a 2 balance factor: log(8) = 4 Actual height: 4 The O(logn) is failing to get over the real height. Could I use this as an argument to disprove this? Where big O notation being the upper bound, should at least be above the real height? I carried it out a few more trees and it seems to be about 22-35% off the real height. Am I still running in O(logn) time? I can't come up with another run time to say : No, its not Logn, its ____ Any suggestions?