Trees - A Non Linear Data Structure

Trees are undirected (without direction) graphs with exactly one path between any two nodes. They are also non-linear data structures that have node-relationships: parent nodes, siblings and children nodes.

Trees are helpful in implementing search algorithms like Breadth-First and Depth-First search. For a graph to be a tree, it should have no cycle, i.e. there shouldn't be more than one path between any two nodes. A graph G is a tree if it satisfies one of the following equivalent criteria:

• G is connected (a path to each node in the graph) and has no cycles.
• A cycle is formed if any two nodes are connected in G.
• G is connected (at least one path to each node), and it is not connected anymore if any edge is removed from G.

For a tree G with n number of nodes, it has n - 1 edges.

 An example of a graph (taken from here):

 I can spot 3 cycles, made of nodes:
- 2,3,4,5
-1,2,5
- 1,2,3,4,5

Now, an example of a tree (taken from here):

In this tree, n (number of nodes) = 7 and number of edges = n-1 = 7-1 = 6 edges