I'm confused with the purpose of the structs here.Can anyone explained.This is a question regarding an implementation of the AVL trees.

struct Node {
int key;
struct Node *left;
struct Node *right;
int height;
};
Does anyone understand this part?

Left and right children. Binary tree can have 2 children, so either you do struct Node** children for 2 items, o name them explicitly. And you traverse down from there

that's my assumption, I never used them, so dbl-check

could you specify your question? and your level of knowledge? because from the perspective of someone who knows what an AVL tree ist (aka "someone who read the wikipedia article about it"), every part of the struct is obvious.

@tosensei Looks more like someone will have exams soon and didn't learn fully how a simple binary tree looks like in C

I haven't used that shit for years, but I've a feeling "struct" is effectively part of the type name i.e. the type name is "struct Node" rather than just Node, or something like that.

A struct is just like a dictionairy, hasmap, named array, object or whatever, maybe that's more familiar to you. In this case, you could see it as a key-value pair that describes a position within a tree. The position in a tree requires more variables so a struct is used.

Maybe the question is about the struct keyword for the fields left and right.

Because I haven’t seen that in C before.

I‘d guess that it’s needed for indirection/recursion.

@Lensflare

It's needed because in C compilers, custom types (aka structs) have "struct" as part of their actual type, and hence you have to refer to subsequent instantiations or pointers as "struct <name>".

Some people hide it by typedef'ing struct X X, but that's generally a bad idea.

@CoreFusionX there is something similar in Swift. The 'indirect' keyword is used if a definition of a custom value type has itself as a "field".
Without that keyword, the size of the type couldn’t be determined, because it recursively depends on itself.
So it introduces an indirection to make it possible.

The other answers are sure to give you all the actionable information, so I'm gonna do it in a more entertaining and far less practical way. And definitely not very precise.

Back in the days of yore, we had this thing called "memory constraints". Processors were so primitive, you could only have a few precious bytes on them. But clients were just as whiny, so we had to get creative.

One cool thing we invented were "structs" - sets of bytes that could be composed of different elements of the regular types, like one or more integers and strings. It is just like a string - a sequence of memory positions - but each few bytes can represent different things and have different types!
Then some MANIAC put an struct inside another struct! To avoid creating a matrix inside the matrix we came up with pointers - do not copy the other struct there, just point at it in the memory, and your original struct only have to contain the bytes of the pointer.

Nowadays we hardly do that. Unless asked to.

@JsonBoa

Pointers weren't made for that. They were meant to enable passing by reference.

You can perfectly have any *declared* struct inside any other struct just fine.

In this particular case you need to use pointers because you can't contain a struct *within itself*, as that would be both ill formed (used before declaration), and lead to an obvious infinite size struct.

@JsonBoa let‘s save gigabytes of data by using pointers everywhere! 😂

@Lensflare

Pretty much all the "top level" languages use pointers, even if they don't expose them to you.

anything not primitive is implicitly passed by reference, which is just passing a pointer by value (hence why pointers exist to enable passing by reference, otherwise it's all by value).

C/C++ simply allow you to declare nonprimitive types on the stack too, with the obvious performance increase, and obvious risks if badly handled.

@CoreFusionX yup. This is what fascinates me about C/C++.
You can declare a type and use it however you like, create on stack or heap, whatever is best for the particular case.

No other language that I know has this feature. Most languages only have reference types with heap allocation. And those languages which also have value types with stack allocation force you to make the decision at the time that the type is declared.

@Lensflare

Well, there are those who think memory management is too critical to be left to the programmer, and those who think it shouldn't be left to the interpreter/computer.

And for most everyday tasks and apps today, with the computing power we have, safety trumps performance IMO...

Yeeeeeeet, let's stop and think what all those marvelous top level languages use...

JS? V8, C++
Python? CPython, C
PHP? Zend engine, C++
C#? .NET CLR, C++
Java? JVM, C++

Even languages which aim to replace C and C++, such as Go, Rust and such, *still* can not completely bootstrap themselves and their runtimes have parts implemented in C or C++.

So yeah, we aren't going anywhere anytime soon, and it's never bad to have at least cursory knowledge of them.

@CoreFusionX having knowledge of C++ gave me invaluable knowledge of how things work. I‘m glad about that, but today I wouldn’t use it for anything.

Those comparisons to other languages almost always miss out Swift, which is an almost perfect compromise of the strengths of C++ and the other high level, convenient syntax languages such as C#, Python or Typescript.

It compiles to machine code, bootstraps itself completely (afaik) and does have automatic memory management without garbage collection.

It‘s so frustrating to me that most people still think that you have to choose between things like performance and ease of use. This is not a fundamental truth. There ARE languages that let you have the cake and eat it, too. Swift is a proof of that.