CODEWITHSUNDEEP
algorithm
ms8
ms8

Reputation: 417

Calculating height of tree provided condition on height of left tree and height of right tree

Suppose We denote leftheight(u) and rightheight(u) the heights of the left and the right subtrees of a node u.

Now if we have a constant c > 0 such that for all nodes u in a tree T, we have 

leftheight(u) ≤ rightheight(u) + c

What can be said about the height of such tree ? Is it O(log n) or what ?

Also, if the condition had been changed to :

leftheight(u)−c ≤ rightheight(u) ≤ leftheight(u) + c

How it will affect the height of tree ?

Upvotes: 1

Views: 87

Answers (2)

user4083064
user4083064

Reputation:

The expressions you put can be rewritten in mathematical form as ::
Ist Part :: A ≤ B + C
IInd Part:: A - C ≤ B ≤ A + C
As C > 0 , i.e. C can be any positive number ,so answer for both part is O(n) .
This is because in Ist Part ,put C=10 and B=0 then A which is leftheight(u) can be 10 and hence tree's height will be 11 with 11 nodes, which is O(n).
Similarly for IIndd part put C=10 and A=0 ,so inequality will be of the form -10≤B≤10 ,now B=10 will satisfy this inequality and hence B which is rightheight(u) will be 10 so height of tree will become 11 ,which again is O(n).

Upvotes: 0

Codor
Codor

Reputation: 17605

To answer the first pat of the question, the height would not be O(log n). Consider a tree with n nodes which is degenerated to a a list by; for every node u, the left subtree is empty and each node (except the single leaf) has a nonempty right subtree, as in the following sketch.

 a
  \
   b
    \
     c

The inequality

leftheight(u) ≤ rightheight(u) + c

holds for every constant c, yet the height of the tree is n.

Upvotes: 1

Related Questions