Tree: is an undirected graph with properties:
- is to be connected graph – there should exist a path between any two nodes/vertices
- no cycles – there should not exist a path in which starting and ending nodes are same
- a simple cycle is formed if any edge is added it – an edge is the connecting link between two nodes.
Example: if a new edge, say between A and D is added a cycle (A-B-D-A) is formed.
- if an edge is removed, it will no more connected.
Example: say if we remove the edge D-E, the graph is no more connected graph and hence no tree.
- any two nodes/vertices should be connected by a unique simple path
For a tree with n nodes/vertices following condition should be satisfied:
- it is connected and has n − 1 edges.
Example: considering Fig. 1, number of nodes (n) = 7 => e=(n-1) =7-1=6.
- has no simple cycles and has n − 1 edges.
Terminologies of tree:
- Internal node/vertex: it (or inner vertex or branch vertex) is a vertex with degree ≥ 2.
In fig. 4 nodes/vertices B, D, E and F with degree ≥ 2 are internal nodes.
- External node/vertex: it (or outer vertex, terminal vertex or leaf) is a vertex with degree = 1.
Example: In fig. 4 nodes A, C and G are External nodes.
- Path:A sequence of nodes traversed from node to node along the edges is called path.
Types of trees
- Rooted tree
- Ordered tree: An ordered tree (or plane tree) is a rooted tree in which an ordering is specified for the children of each vertex.
- Hyper tree