Are Trees Directed or Undirected Graphs?

Question

I have read that Trees are special cases of Graphs. Graphs can be directed or undirected. But if we consider tree as a data structure is it directed or undirected graph?

Contumacy

Answer 1

See Tree on Wikipedia :

A tree is an undirected graph.

Testudinal

Thanks, I should have seen Wikipedia :P – Contumacy

@Testudinal Why not tree cannot be directed graph? – Mcghee

Because there is no dorection defined between the two vertices. – Testudinal

This is false. A tree where each node doesn't hold a pointer to its parent is directed. – Cy

Answer 2

Unless qualified otherwise, trees in Mathematics or Graph Theory are usually assumed to be undirected, but in Computer Science or Programming or Data Structure, trees are usually assumed to be directed and rooted.

You need to be aware of the context of discussion.

Delwyn

Answer 3

Trees are connected acyclic graphs. that means you should be able to traverse from any node u to any node v. If we say trees are directed then it may not be possible to traverse from every node u to every node v.

In context of rooted trees, direction just tells which node of tree is treated as root (starting point) or to show parent child relationship between nodes and that's it all it says ... this direction does not limit the connectivity of graph or a connection between any node u to node v of tree.^[1]

---

^[1] if we considered directions in rooted as actual path which can be traversed in tree to go from node u to node v, then connectivity would be broken and that graph would not be a tree any more.

Dyke

the last sentence is a bit confusing: it's just another illustration of a fact already shown. – Sou

...I transformed the last (illustrating) sentence into a footnote, hope this isn't against the author's intention – Sou

Answer 4

Both are acceptable. You may have some cases where you want to be able to go up from a leaf and then go back down (usually in another branch), or you may want to be able to go only down.

Pedraza

If both are possible(Directed graph and undirected graph) then why wiki is saying only tree is an undirected graph – Mcghee

@VinothKumar The Wikipedia page describes trees in the context of graph theory, where a tree is indeed an special case of an undirected graph. In the context of programming however, what we call trees are most of the time rooted trees with an implied direction from root to leaves. Many algorithms don't need the reverse direction from the leaves to the root, so storing the lighter directed rooted tree is often sufficient. – Pedraza

Agree with your points. Finally tree can be directed graph too. Am i correct? – Mcghee

Answer 5

1-Trees are a subset of graphs.

2-They are undirected acyclic graphs. (Many times we need to go back from leaf nodes to previous nodes to change branches , with unidirectional edges it is not possible)

Colombes