BSTs and other trees - Python Tutorial

- [Instructor] This section is perhaps the most crucial because it forms the absolute foundation of everything we're going to explore throughout this course. But it's also one of the easiest, just a few basic concepts to grasp. And the first concept I want to talk about is the formal definition of a tree. Fundamentally, a tree is any data structure that follows these rules. It has to have exactly one root node. So if a tree has two root nodes, they can't be connected to each other so what you actually have is two trees. If a tree has no root node, then its children aren't connected to anything, or maybe it doesn't have children and then it's nothing. I don't know, anyway, let's just keep it simple. One tree, one root, one root, one tree. Two, each node can have any number of child nodes, can have zero children, in which case we call that node a leaf. It can have 100 children or even infinity children which I guess is a concept more useful for philosophers than software engineers but still this is a valid tree. And three, each node, except for the root, links to exactly one parent. Because if you have a child with two parents, you start getting loops, and remember trees don't have loops. Oh, and while we're at it, a node cannot be its own parent because that's just weird and unnatural. And that's it, any data structure that meets those three criteria is a tree. In practice, there are many different types of trees with additional rules that make them useful. For example, data. Each node in a tree usually has some kind of data associated with it. In a directory structure, for example, this data would be the directory names and files, or other memory pointers to files at the leafs. There are also usually rules about how the nodes are arranged. For example, we can make a tree of words where all the children of the node A must start with the A. All the children of the node AT must start with the AT. And this is a special kind of tree called a trie. And it's actually often used for things like word look-ups. But the kind of tree that we're going to be talking about is the binary search tree. In a binary search tree, each node has only two children called a left and a right child. This is what makes it a binary or two, a two tree. Each node has a value associated with it. Any values to the left of the node must be less than the value of their parents. And any values to the right of the node must be greater than the value of their parents. A tree can also not have duplicated or equal values, each value must be unique. So this results in trees that look like this. This is an example of an illegal binary search tree because the 25 is on the left side of the root. But 25 is obviously greater than 20. Remember, only values that are less than their parents can go on the left. We can fix this by placing the 25 on the right of the tree instead. In fact, if you make a sweep across a binary search tree from left to right, you should find that all of the values are in this numeric order. And if you don't remember the rules right now, that's fine. We are going to go over them again and again and again. So strap in, buckle up, make sure you keep your lefts and your rights straight, and let's head over to the next chapter to start working on some code.