Trees vs. Graphs

Trees and graphs are data structures used to resolve various complex problems. Knowing the difference between them is useful in terms of better understanding of the non-linear way of storing data.

Definition:

Trees and graphs are both abstract data structures. They are a non-linear collection of objects, which means that there is no sequence between their elements as it exists in a linear data structures like stacks and queues.

Trees

A tree is an abstract model and can be defined as a collection of entities called nodes linked together through edges in a hierarchical structure. They don’t have any cyclic relations and there is only one path to a particular node.

Tree data structures have terminology that is worth becoming familiar with:

• Root: the top (initial) node of the tree, where all the operations start
• Node: each item in the tree, usually a key-value
• Edge: a tree has n-1 edges (where n is the number of nodes) representing the connection between two nodes
• Parent: a node which is a predecessor of any node
• Child: a node which is descendant of any node
• Siblings: a group of nodes which have the same parent
• Leaf (terminal) node: a node without children
• Level: it is defined as 1 + the number of edges between the node and the root
• Height: the number of edges from its root to the furthest leaf
• Depth: the number of edges from the node to the tree’s root
• Sub-tree: a portion of a tree data structure that can be viewed as a complete tree in itself

There are different types of trees that you can work with, like Binary Tree, Binary Search Tree, Red-Black tree, AVL tree, Heap, etc. The deciding factor of which tree type to use is performance. Since trees are data structures, performance is measured in terms of inserting and retrieving data.

Graphs

A graph can also be defined as a collection of entities called vertices (or nodes), connected to each other through a set of edges. The set of edges describes the relationships between the vertices. Also, the edges can be given a numerical weight which indicates the strength (or some other attribute) of each connection between the nodes. There can be cyclic relations and more than one path to a particular vertex. Graphs can be directed and undirected depending on whether their edges have a direction.

Important terms related to the graph data structure:

• Vertex: each node of the graph
• Edge: a path or a line between two vertices
• Adjacency: two nodes or vertices are adjacent if they are connected to each other through an edge
• Path: a sequence of edges between the two vertices
• Cycle: a path where the first and last vertices are the same

There are various types of graphs depending upon the number of vertices, the number of edges, interconnectivity, and their overall structure: directed, non-directed, connected, non-connected, weighted, simple, multi-graph, etc.

Examples of application:

• Trees:
  • Manipulate hierarchical data
  • Storing data in a way that makes it easy for searching
  • Represent sorted lists of data
  • Routing algorithms
• Graphs:
  • Manipulating network models
  • Text prediction algorithm
  • Representing dependency of tables in databases
  • Finding the shortest path

Key Differences

• Trees and graphs are mainly differentiated by the fact that a tree structure must be connected and can never have loops while in the graph there are no such restrictions.
• In trees, all nodes must be reachable from the root and there must be exactly one possible path from the root to a node. In graphs, there are no rules dictating the connections among the nodes. A graph contains a set of nodes and a set of edges and edges can be connecting nodes in any possible way.
• In graphs, the number of edges doesn’t depend on the number of vertices. On the contrary, if a tree has “n” vertices (nodes) then it must have exactly “n-1” edges.
• There must be a root node in a tree while there is no such concept in a graph.

Basically speaking, a tree is just a restricted form of a graph (undirected connected acyclic graph). Also known as a minimally connected graph. That makes graphs more complex structures compared to the trees due to the loops and circuits, which they may have.