###### 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

- Polytree
- 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