Four Semesters of Computer Science in 5 Hours, Part 2 Tree Traversals Introduction

Transcript from the "Tree Traversals Introduction" Lesson

[00:00:02]
>> Brian Holt: Moving on to tree traversals. This is pretty important, and if there's one thing that I would say pay attention so you can understand what we're going to talk about for the rest of the day, everything builds on this here. They're all just different applications of the same algorithms.

[00:00:25] Or at least for the next six hours. [LAUGH] So, cool. Let's talk about trees, because computer scientists really like trees. And I do too. So imagine I give you a problem that I want you to take this tree and I want you to make it into a flat array.

[00:00:47] I'm gonna talk about four different ways that you can choose how to do this. So let's just briefly touch again on trees. I talk a lot about it in part one of this course. A lot.
>> Brian Holt: There's binary search trees and then ABL trees and all that stuff.

[00:01:07] So, what you have here pictured in front of you is a binary search tree. I got this graphic off Wikipedia, thanks Wikipedia.
>> Brian Holt: The basic gist is that you have a node, right? Every one of these circles is considered a node, right? This node has a value, right?

[00:01:25] And it has a left child and a right child. Now because this is a binary search tree, That specific thing, binary search tree, also known as BST. So if I say BST, we'll try not to but it just comes out sometimes. Binary search trees have special properties in the sense that everything in the left sub tree, if we're talking about eight right here, everything in this part of the tree.

[00:01:51] Also known as a subtree, because this is still a tree right? If I take off everything over here it's still valid tree, right? So everything in the left sub-tree is smaller than eight everything in the right sub-tree is larger than eight and that's always true for everything in the tree right?

[00:02:10] So if we go down to six, everything in the left sub-tree is smaller, everything in the right sub-tree is bigger. Right, we follow? Cool. That's it, that's all a binary search tree is. They call it a binary search tree because- binary, it has two children. Because there are trees that have more than two children.

[00:02:28] At most two children, I should say. And then it's a search tree because it's designed to be very searchable right? So if I am looking for seven, I don't have to go through everything in the array to get to seven. I can just go through some of them also known as log end.

[00:02:44] Right? That's where the log end parts come into it. If we are talking about Big O. Which if you don't know about Big O, again please go watch the other parts. Because I talk a lot about that. Okay. Questions about BSTs before we move on?