Register

GO Classes DPP | GATE CS, DA | Data Structure | Valid BST and Valid AVL Tree

216 views
6 6 votes

For the following three trees, choose the correct classification.

Tree (a):

Tree (b):

Tree (c):

Which option is correct?

  1. All three are valid AVL trees.
     
  2. Tree (a) is not a valid BST, tree (b) is a valid BST but not a valid AVL tree, and tree (c) is both a valid BST and a valid AVL tree.
     
  3. Tree (a) is a valid AVL tree, tree (b) is not a valid BST, and tree (c) is not a valid AVL tree.
     
  4. Tree (a) and tree (b) are valid AVL trees, but tree (c) is only a valid BST.

1 Answer

0 0 votes

Tree (a): 

This is not a valid BST! The $2$ is located in the right sub-tree of $7$, which breaks the BST property. 

Remember that the BST property applies to every node in the left and right sub-trees, not just the immediate child! 

All AVL trees are BSTs. Because of this, this tree can't be a valid AVL tree either. 

 

Tree (b): 

This tree is a valid BST! If we check every node, we see that the BST property holds at each of them. 

However, this is not a valid AVL tree. We see that some nodes (for example, the $42$) violate the balance condition, which is an extra requirement compared to BSTs. Because the heights of $42$'s left and right sub-trees differ by more than one, this violates the condition. 

 

Tree (c): 

This tree is a valid BST! If we check every node, we see that the BST property holds at each of them.

This tree is also a valid AVL tree! If we check every node, we see that the balance condition also holds at each of them.

Voting & Accepting an answer helps improve the community
Answer:
← Previous · GO Classes DPP | GAT...Next → · GO Classes DPP | GAT...
← Previous in category · GO Classes DPP | GAT...Next in category → · GO Classes DPP | GAT...
Position:
Show:

Related questions

7 7 votes
2 2 answers
374
374 views
GO Classes asked Jul 23
374 views
GO Classes DPP | GATE CS, DA | Data Structure | Valid AVL Trees
Which of the following trees are valid AVL trees? 
6 6 votes
1 1 answer
194
194 views
GO Classes asked Jul 23
194 views
GO Classes DPP | GATE CS, DA | Data Structure | AVL Search Complexity
What is the time complexity for efficiently finding an arbitrary item in an arbitrary AVL tree of $n$ nodes?$\Theta(n)$ $\Theta(\log_2 n)$ $\Theta(n \log_2 n)$ $\Theta(n^...
7 7 votes
1 1 answer
265
265 views
GO Classes asked Jul 23
265 views
GO Classes DPP | GATE CS, DA | Data Structure | AVL Insertion Property
Which statement is true for AVL trees?Adding a node may cause the tree to increase in height. Adding a node will cause the tree to increase in height. Adding a node may c...
5 5 votes
1 1 answer
216
216 views
GO Classes asked Jul 23
216 views
GO Classes DPP | GATE CS, DA | Data Structure | AVL Insertion
We have just inserted $51$ into the following AVL tree. Rebalance the tree.What is the root of the AVL tree after rebalancing?$35$ $42$ $47$ $57$