What will be complexity in this Balanced BST?

Question

I have been asked this question in an interview and I'm curious to know what will be the correct explanation for it?

Consider the following height balanced BST where Balance factor = Height of left subtree - Height of right subtree & the accepted balance factors are 0, 1, -1, 2, and -2. What will be the time taken to search an element in such a kind of height-balanced BST? Explain.

What I said was, even if it has a height factor of 2 rather than 1 in standard Balance BST definitions, still the operations should be logN complexity order, (where N is the number of elements in the tree) because when the N will be large then will be not making much difference if the height factor is 2 or 1.

If anyone can tell me what would have been the correct answer here will be helpful :)

Answer 1

We can solve this mathematically as :

Defining Worst Case

Now, in any Binary Tree, time complexity of searching is O(h) where h is height of the Binary Tree.
Now, for worst case, we want to find Maximum Height.

In case of simple Binary Search Tree with no Balancing Factor Condition on Nodes, this maximum height can be n or n+1 (depending on convention whether height of single node tree will be 1 or 0) where n is number of nodes.

Thus, we can say that given number of nodes, worst case is maximum height.

Interestingly, we can also say that given height of a tree, the worst case is minimum nodes. As even for such minimum number of nodes, we might have to traverse down the tree of height h, which we also have to do for maximum number of nodes.

Thus, the intuition should be clear that Given Height of Tree, the worst case is minimum number of nodes.

Applying this Concept on Binary Search Tree

1. Let us try to construct Binary Search Tree of Height H such that number of nodes in the tree is minimum.

Here we will exploit the fact that Binary Tree is a Recursive Data Structure (A Binary Tree can be defined in terms of Binary Tree)

2. We will use the notation N_H to denote Minimum Number of Nodes in a Binary Search Tree of height H

3. We will create a Root Node
   

4. To Left (or Right) of Root, add a subtree of height H-1 (exploiting Recursive Property). So that number of nodes in entire tree is minimum, the number of node in Left (or Right) subtree should also be minimum. Thus N_H is a function of N_H-1

5. Do we need to add anything to Right (or Left)?
   No. Because there is no restriction of Balancing Factor on BST. Thus, our tree will look like

6. Thus, to construct Binary Search Tree of Height H such that number of nodes in the tree is minimum, we can take Binary Search Tree of Height H-1 such that number of nodes is minimum, and can add 1 root node.
   Thus, we can form Recurrence Relation as
   N_H = N_H-1 + 1
   with base condition as
   N₀=1

To create BST of height 0, we need to add one node. Throughout the answer we will use this convention

7. Now, this Recurrence Relation is quite simple to solve by Substitution and thus
   N_H = H+1
   N_H > H

8. Now, let n be the number of nodes in the BST of height H
   Then,
   n ≥ N_H
   n ≥ H
   H ≤ n
   Therefore, H=O(n)
   Or O(H) = O(n)

Thus, Worst Case Time Complexity for Searching will be O(n)

Applying this Concept on AVL Tree

We can apply similar concept on AVL Tree. After reading later part of solution, one can find recurrence relation as :

N_H = N_H-1 + N_H-2 + 1

with Base Condition :

N₀ = 1
N₁ = 2

And, inequality condition on solving recurrence will be

N_H ≥ ((1+√5)/2)^H

Then, let n be the number of nodes. Thus,

n ≥ N_H

On simplifying, one can conclude that

H ≤ 1.44log₂(n)

Applying this Concept on GIVEN Tree

1. Let us try to construct Given Tree of Height H such that number of nodes in the tree is minimum.

2. We will use the notation N_H to denote Minimum Number of Nodes in Given Tree of height H

3. We will create a Root Node
   

4. To Left (or Right) of Root, add a subtree of height H-1 (exploiting Recursive Property). So that number of nodes in entire tree is minimum, the number of node in Left (or Right) subtree should also be minimum. Thus N_H is a function of N_H-1

5. Do we need to add anything to Right (or Left)?
   Yes! Because there is restriction of Balancing Factor on Nodes.
   We need to add subtree on Right (or Left). What should be it's height?

   H?

   No, then height of entire tree will become H+1

   H-1?

   Permitted! since Balancing Factor of Root will be 0

   H-2?

   Permitted! since Balancing Factor of Root will be 1

   H-3?

   Permitted! since Balancing Factor of Root will be 2

   H-4?

   Not Permitted! since Balancing Factor of Root will become 3

   We want minimum number of nodes, so out of H-1, H-2 and H-3, we will choose H-3. So that number of nodes in entire tree is minimum, the number of node in Right (or Left) subtree should also be minimum. Thus N_H is also a function of N_H-3

6. Thus, to construct Given Tree of Height H such that number of nodes in the tree is minimum, we can have LEFT subtree as Given Tree of Height H-1 such that number of nodes is minimum and can have RIGHT subtree as Given Tree of Height H-3 such that number of nodes in it is also minimum, and can add one Root Node. Our tree will look like
   

   Thus, we can form Recurrence Relation as

   N_H = N_H-1 + N_H-3 + 1
   with base condition as
   N₀=1
   N₁=2
   N₂=3

7. Now, this Recurrence Relation is Difficult to Solve. But courtesy to this answer, we can conclude that
   N_H > (√2)^H

8. Now, let n be the number of nodes in the Given Tree Then,

   n ≥ N_H
   n ≥ (√2)^H
   log_√2(n) ≥ H
   H ≤ log_√2(n)
   H ≤ 2log₂(n)

Therefore, H=O(log(n))
Or O(H) = O(log(n))

Thus, Worst Case Time Complexity for Searching in this Given Tree will be O(log(n))

Hence, Proved Mathematically!