- The Function heightOfParseTree() is used to find out maximum height of Parse Tree by finding maximum heights of left subtrees and right subtrees and adding 1 to it because of root node.
- If it has no right or left subtrees, then maximum height is one as it has only root element.
- If we have only left subtree, then maximum height of parse tree is 1(due to root element)+height of left subtree.
- If we have only right subtree, then maximum height of parse tree is 1(due to root element)+height of right subtree.
- If it has both left and right subtrees and height of left subtree is more than that of right subtree, then the maximum height of parse tree is 1(due to root element) + left subtree.
- If it has both left and right subtrees and height of right subtree is more than that of left subtree, then the maximum height of parse tree is 1(due to root element) + right subtree .
In this case we are recursively calling on the left and right subtrees so the recurrence relation turns out to be
T(n) = T(k) + T(n-k-1) + c, where n is total number of nodes , k is number of nodes on one side of tree and remaining n-k-1 nodes on the other side of Parse Tree and c is a constant.
We have two cases now
- If the tree is Skewed tree then ( all nodes are on one side of the tree)
- then k = 0
- T(n) = T(0) + T(n-1) + c , as T(0) is a constant let it be d
- T(n) = T(n-1) + (c+d) , let c+d = a which is another constant
- T(n) = T(n-1) + a
- Now on solving this recurrence relation we get,
- T(n-1) = T(n-2) + a
- T(n-2) = T(n-2) + a
- T(n-3) = T(n-4) + a
- and so on....
- T(n) = na
- O(n) is Time complexity for this case
- If the given tree is balanced then (equal number of nodes on both sides)
- T(n) = 2T(n/2) + k
- T(n/2) = 2T(n/4) + k
- T(n/4) = 2T(n/8) + k
- .... and so on
- On solving this recurrence relation we get T(n) = 2^(log(n)) , where log(n) has base 2
- So T(n) = n
Therefore Time Complexity turns out to be O(n) for this recursive function.
Space Complexity is O(1) as we are not using any auxiliary space for this function, only stack memory is being used for recursive calls.