Tree (Data Structure)

Tree

         Tree can be defined as a finite set of vertices(nodes zero or more) such that:

-       There is one specially designed vertex called root.

-       The remaining vertices are partitioned into a collection of subtrees wich are also trees.

-        An edges/arcs/branch is a connection between two vertices. 

     The nodes of a tree have a parent child relationship. The root doesnot have a parent but each of the other nodes has a parent associated to it.

A node may or maynot have children. A node that has no children is called leaf/terminal/external node. Nodes with atleast one child are called non-leaf/non-terminal node.

If a tree has n nodes, one of which is the root node then there must be (n-1) edges.

 

 Basic terms

1.      Siblings

Nodes with same parents are called siblings. For example 4 and 12, 2 and 6 and some others are siblings.

2.      Path

A path is a list of distinct vertices in which successive vertices are connected by edges in the tree. There is exactly one path between the root node and each of other nodes in the tree. If there exists more than one path between the root and some other nodes or there is no path between the root and some other node, then the given structure is not a tree.

For example: the path from 8 to 11 is

8-12-10-11

3.      Path length

The length of any path is the no of edges on the path. For example: the length of the path from 8 to 11 is 3

1.      Depth

Depth of any node n is the length of the path from the root node upto the node n. the root is at always at depth zero. For example the depth of node 10 is 2.

2.      Height

The height of any node n is the height of the longest path from node n to a leaf node. All leaves are always at height zero. For example the height of node 12 is 2.