# Tree Questions: Example

Which of the following five statements is incorrect?
• A binary tree whose subtrees have exactly the same height (or alternatively called depth) is an AVL tree.

False: the following tree has subtrees of the same height, but is not AVL, since only the topmost node is balanced:

```              Node 0 5
/        \
Node 2 4    Node -2 6
/    \        /    \
Node 1 3  Leaf  Leaf  Node -1 7
/    \               /   \
Node 0 2  Leaf         Leaf  Node 0 7
/    \                     /    \
Leaf   Leaf                Leaf    Leaf
```
• Searching in a perfectly balanced ordered binary tree requires O(log n) steps

True

• Inserting a new element into an AVL tree requires on average more steps than inserting an element into an ordinary ordered binary tree.

True: to preserve the AVL property, it might be necessary to rotate the nodes which requires a constant number of additional steps.

• Every tree with a height of at most two is an AVL tree.

True: The two subtree can have at most height 1, so they height cannot differ by more than 1.

• Searching in a degenerated ordered binary tree, that is a tree with maximal height, has the same work complexity as searching in a list.

True: A degenerated tree has the same shape as a tree. It's height is propotional to the number of nodes.

Gabriele Keller