Binary tree traversals and related properties binary tree
Binary tree traversals
and related properties binary tree
Binary Tree:
Definition of binary tree itself divides the tree into two sub-trees. Many problems about binary trees can be solved by applying the divide and conquer technique
Example 1:
Write an algorithm to find the height of a given binary tree.
Solution:
ALGORITHM BinTreeHeight ( T )
//computes recursively the height of a binary tree
//i/p: A binary tree T
//o/p: Height of T
Analysis:
• Input size: number of nodes
• Basic operation:
o Number of comparison made to compute the maximum of two numbers
o Number of additions made
• No best, worst, average case
• Let n(T) be the number of nodes in the given binary tree. Since comparison & additions takes place equally; considering only number of additions, we have the recurrence:
Solving the recurrence we have A(n) = n
Comments
Post a Comment