Generic doubt about Trees in data structure subject.
in DS edited by
71 views
1 vote
1 vote
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.
in DS edited by
by
9 points
71 views

1 Answer

1 vote
1 vote

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
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.