What's the difference between the data structure Tree and Graph?

user918304 picture user918304 · Sep 14, 2011 · Viewed 96.4k times · Source

Academically speaking, what's the essential difference between the data structure Tree and Graph? And how about the tree based search and Graph based search?

Answer

user785287 picture user785287 · Oct 10, 2011

A Tree is just a restricted form of a Graph.

Trees have direction (parent / child relationships) and don't contain cycles. They fit with in the category of Directed Acyclic Graphs (or a DAG). So Trees are DAGs with the restriction that a child can only have one parent.

One thing that is important to point out, Trees aren't a recursive data structure. They can not be implemented as a recursive data structure because of the above restrictions. But any DAG implementation, which are generally not recursive, can also be used. My preferred Tree implementation is a centralized map representation and is non recursive.

Graphs are generally searched breadth first or depth first. The same applies to Tree.