Question

In a binary tree, the balance ratio of node v, bal(v), is the number of nodes in the left subtree of node v divided by the sum of the number of nodes in the right and left subtrees of node v. bal(a leaf node) = ½. A tree T is said to be ε-balanced if, for all nodes v in T, ½ - ε < bal(v) < ½ + ε.

Design an efficient recursive algorithm that determines whether a binary tree is ε-balanced. What is the time complexity of your algorithm?

Answer 1

• The above algorithm receives a binary tree T and a constant ε.
• If T is null(tree with no nodes), algorithm returns 0. That is, T is obviously ε-balanced.
• If T is not null, then the algorithm is recursively called to determine whether the given binary tree is ε-balanced or not.
• If T is ε-balanced , algorithm returns a non-negative number that represents the number of nodes in the given binary tree. Otherwise, algorithm returns -1.
• If T contain only one node and it is ε-balanced, then algorithm returns 3, since algorithm considers null nodes also.
• In each recursive call, algorithm finds the number of nodes in the left sub tree and the number of nodes in the right sub tree.
• If either the left sub tree and right sub tree is not ε-balanced, then the algorithm returns -1.
• Otherwise, it calculates balance ration(bal(v)) of the current node(v). if ½ - ε < bal_v < ½ + ε , then the algorithm returns the sum of the number of nodes in the right and left subtrees of node v plus 1. Otherwise, algorithm returns -1.

Time complexity:

• The above algorithm traverses each node and calculates the balance ration of each node.
• In the worst case(line 11-13), algorithm is called recursively on left sub tree and right subtree. Thus, the recurrence relation that represents the time complexity of the algorithm is as follows:

T(n)=T(k)+T(n-k-1)+c

Where, n=number of nodes in the binary tree, k=number of nodes in the left sub tree and n-k-1= number of nodes in the right sub tree. Also, T(0)=c

• Guess the solution for the above recurrence. Assume T(n) ≤ cn =O(n)

Prove this using induction:

Base step: (c)0 + c= c = T(0) as defined above.

Inductive hypothesis: Suppose that T(m) ≤ (c )m + c for all m < n

Inductive step:

T(n) ≤ T(k) + T(n−k−1) + c
      = (ck) + c(n−k−1) + c
= c(k + n − k − 1) + c
= c(n − 1) + c
= cn−c+c
= cn

Therefore, the time complexity of the above algorithm is O(n).