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

image

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:

image

Solving the recurrence we have A(n) = n

Comments

Popular posts from this blog

Data Structure Visualization:Introduction and Value of Data Structure Rendering

Binary Space Partitioning Trees:BSP Tree as a Hierarchy of Regions.

Drawing Trees:HV-Layout