PROBLEM 1: Suppose a (vanilla) Binary Search Tree contains the keys {1, 2, 3, 4,

Question

PROBLEM 1: Suppose a (vanilla) Binary Search Tree contains the keys {1, 2, 3, 4, 5 and the tree has the structure below. Part-A: Your job: correctly assign the keys to the nodes Part-B: What Insertion sequence results in the structure above? Part-c: In your sequence above which is the first insertion (if any) that results in a violation of the AVL properties? Part-D: The tree above has height 4. How many valid Binary Search Trees containing the values 1, 2, 3, 4, 5 have height 4 (including the one given)? Show your reasoning

Explanation / Answer

A AND B) 1, 5,2,4,3 is the Insertiuon Order

=> 1 is the root, 5 is the right child of 1
=> 2 is the left child of 5
=> 4 is the right child of 2
=> 3 is the left child of 4


C)After Insertion of 2, Tree is Unbalenced,
Since height of Root is unbalanced




D) To get height 4, we need to put either 1 or 5 at root.

So count can be written as T(n) = 2*T(n-1) with T(1) = 1

Hence the number of valid BST is : 24 = 16

Thanks, let me know if there is any concern.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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