Trees: An Introduction

Trees are very flexible, versatile and powerful non-liner data structure that can be
used to represent data items possessing hierarchical relationship between the grand father
and his children and grand children as so on.


The topmost node is called root of the tree. The elements that are directly under an element are called its children. The element directly above something is called its parent. For example, a is a child of f and f is the parent of a. Finally, elements with no children are called leaves.

Advantages of Trees

1. Trees can serve as a hierarchy 
2. Trees provide moderate access/search
3. Trees provide Moderate/insertion Deletion
4. Have no upper limit 

Main applications of trees include:

1. Manipulate hierarchical data.
2. Make information easy to search .
3. Manipulate sorted lists of data.
4. Router algorithms
5.  Form of a multi-stage decision-making.

A Tree Classification

---

Binary Tree

A tree whose elements have at most 2 children is called a binary tree. Since each element in a binary tree can have only 2 children, we typically name them the left and right child.

It can be represented as:  

1. Data 
2. Left pointer or Child
3. Right pointer or Child

Properties of a Binary tree

1) The maximum number of nodes at level ‘l’ of a binary tree is 2^(L-1).

Here level is number of nodes on path from root to the node (including root and node). Level of root is 1. This can be proved by induction.For root, L = 1, number of nodes = 2^(L-1) = 1.Assume that maximum number of nodes on level l is 2^(L-1).Since in Binary tree every node has at most 2 children, next level would have twice nodes, i.e. 2 * 2^(L-1)

2) Maximum number of nodes in a binary tree of height ‘h’ is 2^h – 1.

Here height of a tree is maximum number of nodes on root to leaf path. Height of a leaf node is considered as 1.

This result can be derived from point 2 above. A tree has maximum nodes if all levels have maximum nodes. So maximum number of nodes in a binary tree of height h is 1 + 2 + 4 + .. + 2^h-1. This is a simple geometric series with h terms and sum of this series is 2^h – 1.

3) In a Binary Tree with N nodes, minimum possible height or minimum number of levels is  ⌈Log(base2)(N+1)].

This can be directly derived from point 2 above. If we consider the convention where height of a leaf node is considered as 0, then above formula for minimum possible height becomes   

⌈ Log(base2)(N+1)⌉ – 1

4) A Binary Tree with L leaves has at least   ⌈ Log2L ⌉ + 1   levels

A Binary tree has maximum number of leaves when all levels are fully filled. Let all leaves be at level l, then below is true for number of leaves L.

   L   <=  2l-1  [From Point 1]

   Log2L <=  l-1

   l >=   ⌈ Log2L ⌉ + 1  

5) In Binary tree, number of leaf nodes is always one more than nodes with two children.

   L = T + 1

Where L = Number of leaf nodes

      T = Number of internal nodes with two children

Types of Binary trees:

1. Full Binary Tree ; A full binary tree is a binary tree which has exactly has either 2 children or  no children. (No. of leaf nodes=No, of internal nodes+1)
2. Complete Binary Tree: A complete Binary tree is a binary tree excepting the bottom which is filled from left to right.Its the best binary tree as it provides the best possible ration between the number of nodes and the height. O(log N) height h and nodes N. 2^(h+1)-1.
3. Strictly Binary tree: A strictly binary tree is a binary tree which has 2N -1 nodes i.e., no children or two children where N stands for degree.
4. Perfect Binary Tree:A perfect binary tree is a binary tree in which all interior nodes have two children and all leaves have the same depth or same level.They are ambiguously also known as complete or full binary tree.
5. Balanced binary Tree:A balanced binary tree has the minimum possible maximum height (a.k.a. depth) for the leaf nodes, because for any given number of leaf nodes the leaf nodes are placed at the greatest height possible.

Tree Traversal 

Unlike other linear data structures, trees can be traversed in different ways.The ways to traverse trees are : 

1. Depth First Search 
1. Inorder Traversal     (Lc R Rc) //Where Lc=Left Child Rc= Right Child R=Root
2. Preorder Traversal   (R Lc Rc) //                   "
3. Postorder Traversal (Lc Rc R) //                   " 
2. Breadth first Search

References

More tree explanations shall be done with programs.

If you are given two traversal sequences, can you construct the binary tree?
It depends on what traversals are given. If one of the traversal methods is Inorder then the tree can be constructed, otherwise not.

Therefore, following combination can uniquely identify a tree.

Inorder and Preorder.
Inorder and Postorder.
Inorder and Level-order.

And following do not.
Postorder and Preorder.
Preorder and Level-order.
Postorder and Level-order.

For example, Preorder, Level-order and Postorder traversals are same for the trees given in above diagram.

Preorder Traversal = AB
Postorder Traversal = BA
Level-Order Traversal = AB

So, even if three of them (Pre, Post and Level) are given, the tree can not be constructed.