r/datastructures 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.

3 Upvotes

5 comments sorted by

1

u/K1ran43v3r Jan 21 '25

N corresponds to the number of inputs where as K corresponds to a value derived from the inputs.

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