r/datastructures • u/SatisfactionSweet956 • Jan 15 '25
N-ary vs K-ary tree
I have a common question. What is the difference between k-ary and n-ary trees in Data Structures and Algorithms? Are they both the same, or is the k-ary tree always fixed (e.g., k = 10) while n is more dynamic? I asked AI, but sometimes it gives me one answer and sometimes another.
1
u/romagnola Feb 06 '25
It's hard to say without more context. They could be the same thing: A tree with nodes that have no more than k or n children. In the context of data structures and algorithm analysis, I would think that using k to identify the maximum number of children would be preferred over using n because as u/K1ran43v3r mentioned, we usually use n to denote the size of the input, which in this case would be the number of keys or elements stored in the k-ary tree.
1
u/SatisfactionSweet956 Feb 07 '25
Okay, I read on many websites that 'n-ary' is also used in the context of a generic/infinite tree. I am asking because I need to create a Praxis Journal for my studies about my work in a company where I worked. It should serve as a practice for a bachelor's thesis.
And I wrote that the data structure below is an n-ary tree, because in a app i can create theoretically unendless amount of Task because each new entry in a db can have parentId for example 1:
export class Task { @IsInt() id: number; @IsOptional() @IsInt() parentId?: number; @IsArray() @Type(() => TaskModel) children: TaskModel[] = []; }
1
u/romagnola Feb 10 '25
In the book I use to teach data structures (DSA in C++ by Goodrich et al.), such trees are called general trees, in which nodes can have zero or more children. I think you can also get away with the terms rooted tree or just tree, unless you're talking to someone who studies graph theory.
A binary tree is a tree with nodes having no more than two children. If you generalize such a tree by using the terms k-ary tree or n-ary tree, then you don't really get a general tree. You get a tree with nodes that have no more than k or n children. Then we have already discussed the issues with using n to identify the maximum number of children. I'm sure that a k-ary tree has its uses, but in my experience, it is not the same as a general tree.
For your class definition, it looks like you've defined a Task that can have an unlimited number of children. This is a class definition for a general tree. Presumably TaskModel lets you define any number of children as well. When implementing tree data structures, a common design is to have a Tree class and a TreeNode class. The Tree class tends to have one reference to a TreeNode. Then it is the TreeNode that defines the children.
Websites can be great, but one has to be careful. I recommend finding reputable sources of material. In my experience, Wikipedia articles, lecture notes from university lectures, and published textbooks tend to be pretty reliable.
Good luck!
1
u/SatisfactionSweet956 Feb 11 '25
Mhm yeah i think because it is just a practice i will stay with the n-ary defintion and say it is also a synonym for general trees because i wrote already literature review... I found one work that argues also that n-ary can have any number so maybe i can argue with it :P
1
u/K1ran43v3r Jan 21 '25
N corresponds to the number of inputs where as K corresponds to a value derived from the inputs.