We define the height(v) of a tree rooted at v to be the length of the longest pa

Question

We define the height(v) of a tree rooted at v to be the length of the longest path from the root to a leaf (if two nodes are connected by a path, the length of the path is the number of edges along this path). An alternative way of defining the height h(t) of a tree t is

• if t is empty or just a single node (i.e. the root is also the single leaf), h(t) = 0

• if t is not just a single node then h(t) is one plus the maximum of the heights of its children.

(a) (10 points) Give pseudo-code for a DIVIDE-AND-CONQUER algorithm to find the height of a binary tree. For a tree t, you can use in your pseudo-code lef t(t) and right(t) to denote a left and right sub-trees of non-empty tree t. use n(t) to denote the number nodes of t .

(b) (5 points) Suppose that in the binary tree given for the initial input all of the nodes have no right child (the binary tree is degenerate). Give a recurrence for T(n) where T(n) is the time complexity of your algorithm when the tree has n nodes. Then give a tight asymptotic bound for T(n).

(c) (5 points) Now suppose that in the binary tree given for the initial input is a complete binary tree (Meaning that at a given level either all of the nodes have two children,both left and right, or all of the nodes are leaves. For such a tree the left and right subtree 1 have the same number of nodes.) Give a recurrence for T(n) where T(n) is the time complexity of your algorithm when the tree has n nodes. Then give a tight asymptotic bound for T(n).

Explanation / Answer

a) Pesudocode for divide and conquer

    int height(root){ // root is the root of the tree

        if (root is NULL)
           return 0
        else
           return 1 + max(height(left(yt)), height(right(t)) //max gives the maximum value of all given inputs
    }

b) If we have a binary tree with only right child , it will become a skwewed tree
    T(n) = 1 + T(n-1)

    So for n number of nodes
     T(n) = n

c) In case of balanced binary tree we have
    T(n) = 1 + T(n/2)

   At each level tree is getting divided by two and number of nodes are getting reduced by half.In this case the height of the tree with n nodes = log(n)
   

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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