Tree: is an undirected graph with properties:

Fig. 1: Connected Graph

• 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.
  
  

  Fig. 2: Cycle by adding a new edge

• 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.
  
  

  Fig. 3: disconnected graph if edge removed

• 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.
  
  

  Fig. 4: Internal Nodes (B, D, E and F 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