All right, I want to start talking about a very exciting topic, and that is trees. And you'll soon start to realize that there are tons and tons and tons of tree data structures. But today I want to focus on a very popular country and that is binary trees. And with binary trees, we must talk about binary search trees as well. So today's tutorial is going to focus on binary trees and binary search trees where they're used and what they are. And in later tutorials, we're going to cover how to insert nodes into binary search trees, remove nodes, and also do some of the more popular tree traversals which can apply to other general trees also, not just binary trees.

Okay. So I'm going to give you guys a quick crash course on trees before we get started. So we see a tree is an undirected graph which can satisfy either of the following definitions there are actually multiple definitions, but these are the most popular ones. So trees and a directed graph, which is connected and a cyclic. A cyclic means there are no cycles. Another definition is we have n nodes, but we have n minus one edges.

And lastly, for any two vertices, there's only one path between those two vertices, you can't have two different paths. That would imply that we don't have a tree because there's another route to get to another node. And so we'd have a cycle. Okay, and context trees. We have something called a rooted tree, which is the topmost note of our tree, you can think of it that way. And if you tried to root the tree, and you don't have a root yet, it doesn't matter which node you pick to root tree, because any node you pick can become the root node.

Think of it as picking up the tree by that node. And suddenly, it's the new root. We have something called are the concept of child and parent nodes. So a child node is a node that extends from another node. Think of it as going downwards and a parent node is the inverse of this. So you're going up towards the root.

So we have an interesting question and that is, what is the parent of the root node? The answer is that the root node has no parent. Although sometimes it may be useful to say that the parent of the root node is itself. And we see this often when programming, for instance, a file system. tree has this property. So if I open up the command line, I'm in some directory, so I can say pwd the current directory.

So I'm somewhere in the file system tree. And if I want to go up to my parent, I can say CD dot dot slash, and now I'm up in another directory or in to the parent directory. And I can keep doing this and going up and up in the file system tree directory system. But if I go directly to the root node, which is slash, I see that I'm in the folder slash so the very top at the root of the directory Sa CD dot dot, then if I check out where I am, I am again at the root. So, in this context, for a file system, the parent of the root is the root. Pretty cool.

So just as an example, if we pick the node zero, it has two children, three and two and a parent four. We also have the concept of something called a leaf node, this a node which has no children, and these have been highlighted in orange. So there are just at the very bottom of your tree, think of it that way. And there's also another term, which is sub tree. This is the tree entirely contained within another tree. And we usually use triangles to denote sub trees.

It's possible for a sub tree which consists of only a single node, so that's fine. So if this search tree with that circle node Being the root, and we pick a particular sub tree and look what's inside of it, then we get another tree, which contains nodes and more sub trees. Then we pick another sub tree look with inside of it, and then we get another tree. And eventually we're going to hit the bottom. So now we can pose the question, what is a binary tree? This is simple.

This is a tree in which every node has at most two children. So both those trees below our binary trees, because they have at most two children, you can see that the tree on the right eat has one child, and that's fine, because the criteria is at most, two. Now I'm going to play a game. I'm going to give you some various structures, and you're going to have to guess whether it is a binary tree. Or not? So is this a binary tree?

Yes, yes it is. every node has at most two children. How about this one? No, you can see that seven has three children. So it's not a binary tree. How about this one?

Let you guys think about it a bit more. Yes, this is a binary tree. It may be a degenerate one, but it's still a binary tree. Alright, let's move on to binary search trees. So what is a binary search tree? Well, first of all, it's a binary tree.

But Furthermore, it also satisfies what's called the binary search tree invariant. And that is that the less left subtree has smaller elements, then the value of the current node and the right subtree has larger elements than that of the current node. So below are a few binary search trees. We're gonna play the same type of game. And I'm going to give you some trees and you're going to have to guess whether they're binary search trees or not. What about this structure?

And this one, we could say it depends on whether you want to allow duplicate values inside your tree. It so happens that binary search tree operations allow for duplicate values. There's nothing wrong with that. But most of the time, we're only interested in having unique values inside our tree. So this particular tree depends on what your definition of a binary search tree is. How about this?

Tree? Yes, this is a binary search tree. How about this tree? Notice I've only changed the elements within the tree. Yes, this is also by area surgery. We're not limited to only having numbers within our binary search tree, we can place any type of data which is comparable and can be ordered.

How about this tree? No, this is not a binary search tree. And the recent is the, the node nine is in the wrong position. When we would be inserting nine, we would have to place it in the right subtree of eight because nine is larger than eight so it belongs in its right subtree. How about this structure? This structure isn't even a tree actually, because it contains a cycle.

And the requirement to be a binary search tree is that you must be a tree This last one, I'm going to give you a bit more time to look at this one. Because it's not a regular type of structure you might think of as a binary search tree. And the answer is yes, this structure does satisfy the binary search tree invariant that every right subtree contains larger elements. You will, you'll see that that is true. And also every left subtree that contains smaller elements. It doesn't look like a tree, but it's as our definitions of a tree and a binary search tree.

Okay, so we've been talking about by trees, binary search trees, where they used Why are they useful? So in particular, binary search trees are used in many implementations of abstract data types for sets and maps and so on. They're also used to implant balanced binary search trees, which we'll probably get to in a later video. Can you see binary search, or sorry, binary trees in binary heaps. We've already seen this in priority queues when we're making a binary heap. But we also see binary trees and things like syntax trees.

So you're parsing an arithmetic expression, then you place it in an abstract syntax tree. And then you can simplify your expression. compilers and calculators use this to evaluate expressions. So wherever you punch in your calculator gets parsed into binary tree and evaluated. And lastly, I just threw in a tree, which is another type of probabilistic data structure. So now let's look at the complexity of these binary search trees because they looked very interesting and also very useful.

And indeed they are. So in the app average case, when you're just given some random data, the time complexity is going to be logarithmic, which is really good. So if you're inserting nodes, deleting nodes, removing nodes searching for a value tree, whatever, the average time complexity is going to be logarithmic. And these binary trees are binary. So trees are very easy to implement. So this is really good.

However, in the worst case, if your tree and T generates to being a line, then we can have some linear behavior going on, which is really bad. So there's some trade offs if you want to use just a pure binary search tree, that it's going to be easy to implement. And on average, it's going to have this logarithmic behavior but in the worst case, you might be looking at some linear stuff. Which is not so good. Okay, in future videos, we're going to look at how to insert things into binary search trees. That's going to be the next video actually.

So stay tuned for that. And also feel free for some source code, I put a link to my repository of data structures. It should also be in the description, guys, thanks for watching and stay tuned.