Data Structures and Algorithms Problem An AVL tree is a BST in which the balance

Question

Data Structures and Algorithms Problem

An AVL tree is a BST in which the balance factor of every node, which is defined as the difference between the heights of the node's left and right subtrees, is either 0, or +1, or -1. In Figure 1, only the tree in part (a) is an AVL tree; (b) has two nodes (4 and 6) that violate the balance requirement; (c) is not a binary search tree because 2 is in the right subtree of 3, and 7 is in the left subtree of 6. For a n = 1,2,3,4, and 5, draw all the binary trees with n nodes that satisfy the balance requirement of AVL trees. Draw a binary tree of height 4 that can be an AVL tree and has the smallest number of nodes among all such trees. (It needs to be a BST.)

Explanation / Answer

http://postimg.org/image/r06950o1j/

http://postimg.org/image/ryjya41tx/

Let me know in case you have any doubt.

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.