71 views
I have a very generic doubt about the Trees concept in Data structures subject, Are Trees in the subject implicitly assumed to be directed unless mentioned otherwise? Say for example, with Binary Trees or K-ary Trees the degree of child nodes are taken to be 0 without explicitly stating that the Tree is directed, Am I missing something.

## 1 Answer

The trees we study in Algorithm subject OR in data structure subject are Rooted Trees.

Now,  Graph Theory from Discrete Mathematics has answer to your doubt :

Rooted Trees are Very Special type of Directed Graphs. Rooted tree is a Directed Acyclic Graph with some more properties like there should be a Root node, and concepts like Children etc.

Rooted trees, even though directed, are usually represented without direction when context is clear that we are talking about rooted trees.

Are Trees in the subject implicitly assumed to be directed unless mentioned otherwise?

YES.

Rooted trees, even though directed, are usually represented without direction when context is clear that we are talking about rooted trees.

Binary tree is a Rooted Tree in which every node has at most two children. So, binary tree, K-ary tree etc are also Rooted Trees.

Say for example, with Binary Trees or K-ary Trees the degree of child nodes are taken to be 0 without explicitly stating that the Tree is directed, Am I missing something.

You are not missing much. Actually you have given it a thought which most of the students do not do.

In Graph Theory, Tree is a undirected connected acyclic graph. Also the term “Degree” is defined only for Undirected Graphs, NOT for directed graphs. For directed graphs, we define “In-Degree, Out-degree ” etc terms, But not “degree”.

BUT since Rooted Trees are VERY special and important class of graphs, they have their own Terminology.

For Rooted tree, even though they are directed, we define the term “Degree”. Degree of node in Rooted Tree is the number of children of that node.

NOTE that in Data Structures or Algorithm subjects, By “Tree” we mean “Rooted Tree”.

Let me know if any more confusion.

by
1.7k points