1
00:00:00,500 --> 00:00:07,640
‫So now we're going to do tree traversal and this is the traversal of a binary search tree.

2
00:00:07,940 --> 00:00:12,800
‫And by traversal, I mean that we're going to visit each node.

3
00:00:13,040 --> 00:00:19,820
‫And what we're going to do is when we visit a node, we're going to do a see out with the value and

4
00:00:19,820 --> 00:00:22,580
‫print out all of the values and the tree.

5
00:00:22,940 --> 00:00:30,590
‫Now, traversing a tree is a little more complicated than traversing something like a linked list with

6
00:00:30,590 --> 00:00:31,350
‫a length list.

7
00:00:31,370 --> 00:00:37,280
‫You're always going to start with the first item and then just traverse through the linked list.

8
00:00:37,490 --> 00:00:42,560
‫But with a tree, there are multiple ways that we can visit each node.

9
00:00:42,650 --> 00:00:48,530
‫So, for example, we could do this row by row where we start at the top, and then we print out the

10
00:00:48,530 --> 00:00:54,200
‫values in the next row and then print out all of the values and the next row.

11
00:00:54,500 --> 00:00:59,630
‫That would be an example of what is called breadth first search.

12
00:00:59,930 --> 00:01:06,860
‫But instead of starting at the top and going row by row, we could do something where we start all the

13
00:01:06,860 --> 00:01:14,450
‫way to the bottom left and then come up and then go down and then come all the way back to the top and

14
00:01:14,450 --> 00:01:19,400
‫then go to the bottom left of the remaining items and then come up and then come down.

15
00:01:19,640 --> 00:01:24,860
‫And this would be an example of what is called depth first search.

16
00:01:24,980 --> 00:01:30,920
‫And we're going to actually do three different types of depth first search.

17
00:01:31,650 --> 00:01:35,820
‫And that is our quick intro to Tree Traversal.