Trees are also Graphs

In this video we discuss a specific type of graph - the binary tree. In the video we discuss some of the properties of a tree that make is a special type of graph, and then we discuss a few common properties of trees that aren’t always present, but are often there in order to make trees a more optimal data structure to work with. This is all used to set the stage for upcoming videos where we start to implement some algorithms first using trees, and then later on more general graphs.

This post is part of the Let's Learn Algorithms series where we learn how algorithms work, see how to implement them, and then spend some time working on practice problems to reinforce how the implementation details work, as well as to help you learn to recognize problems that could be solved using any particular algorithm.

This particular tutorial is part of the section on Graph Theory where we discuss all of the basics about a graph and slowly build our way up to more advanced graph algorithms. This is the first video in the series, so if you are new just sit back and enjoy!

Ready to watch the next video in the series? Depth First Search (DFS) on a Binary Tree

You can view all of the videos in the Let's Learn Algorithms Graph Theory subsection to see if there is one covering a particular topic you are interested in. You can also check out the transcripts for the video below.

• 0:00 - so now that we've sort of covered what a
• 0:02 - graph is and all the different parts of
• 0:04 - it I want to talk about a specific type
• 0:08 - Oh graph and this is a tree now trees
• 0:12 - are special in the sense that they have
• 0:14 - a few properties about them that make
• 0:16 - them easier to work with in a lot of
• 0:18 - ways and that's why to get started we're
• 0:21 - going to sort of just use trees for the
• 0:22 - algorithms we're learning and then once
• 0:24 - we get a feel for them we'll sort of see
• 0:26 - how these algorithms can be used in
• 0:27 - other graphs but I just want to start
• 0:29 - with the trees because they're much much
• 0:31 - easier to work with so the first thing
• 0:34 - that makes a tree easier to deal with is
• 0:35 - that it has a root node so in other
• 0:38 - graphs for example if I go back to the
• 0:40 - map there's no specific City you have to
• 0:42 - start at so any algorithm we sort of
• 0:44 - work with has to keep in mind that you
• 0:45 - can start anywhere and you might be
• 0:47 - going anywhere but when you get to a
• 0:48 - tree you've got this root node and
• 0:50 - that's pretty much where you're always
• 0:52 - going to start you're going to start at
• 0:53 - this route and you're going to work your
• 0:54 - way down the tree
• 0:56 - now the next thing I just sort of
• 0:59 - alluded to is the fact that the edges
• 1:01 - are directed now what this means is that
• 1:04 - when you start at the root node you're
• 1:05 - going to work your way down the tree and
• 1:07 - that is why you're almost always going
• 1:10 - to see treat trees you visually
• 1:12 - represented like this one here where
• 1:14 - you've got a root node up top and then
• 1:15 - it sort of goes downwards to the leaf
• 1:17 - nodes the Leafs are or the leaves are
• 1:20 - these bottom ones the nodes that have no
• 1:22 - children are typically called leaf nodes
• 1:24 - the next thing that I want to mention is
• 1:27 - hard to sort of show visually but it
• 1:29 - stems from the fact that we have a root
• 1:32 - node and our edges are directed and
• 1:34 - they're always directed downwards so
• 1:36 - trees will pretty much never have cycles
• 1:39 - so this means they're directed graph
• 1:41 - they are a cyclical and that's where
• 1:44 - you'll commonly hear the term dag daj
• 1:46 - which stands for directed a cyclical
• 1:48 - graph so trees are pretty much always
• 1:50 - Daggs because you always have to go
• 1:52 - downwards and these are always directed
• 1:54 - edges so there's no way to go from a six
• 1:56 - up to an eight in this case because all
• 1:58 - of our edges go downwards so this is
• 2:02 - really handy because when we start
• 2:03 - working on you know so different
• 2:05 - algorithms and stuff like that dags make
• 2:07 - them much much easier to work with
• 2:09 - because you don't have to worry about
• 2:10 - cycles or preventing them and things
• 2:12 - like that you just sort of go through
• 2:14 - your code and you just move forward and
• 2:15 - you're fine
• 2:17 - so these last two properties that I'm
• 2:20 - going to cover are not always true but I
• 2:23 - think they're sort of worth looking at
• 2:24 - just so you can you pay attention to
• 2:26 - them and you sort of get a feel for them
• 2:28 - the first is that it's common to see
• 2:30 - trees that are balanced so trees by
• 2:33 - themselves aren't naturally balanced but
• 2:36 - there are specific types of trees and
• 2:37 - data structures that create these trees
• 2:39 - that will learn about later that always
• 2:41 - helps sort of create a balanced tree
• 2:43 - what I mean by a ballast tree is that
• 2:46 - when you look at any single node like
• 2:48 - this aight the number of children on the
• 2:50 - left-hand side of that node and the
• 2:51 - number of children on the right-hand
• 2:53 - side are roughly equal now in this case
• 2:55 - they're exactly equal but I say roughly
• 2:57 - because if you had one less child on the
• 2:59 - right side they would still be a
• 3:00 - balanced tree it's just you can't do
• 3:02 - half of a note on each side so you're
• 3:04 - you have a little bit of an offset the
• 3:07 - last thing that I want to talk about is
• 3:08 - again not something that's always the
• 3:10 - case but it's very common to see trees
• 3:13 - that are in a specific order this is
• 3:16 - especially true with like a binary
• 3:17 - search tree or different trees like that
• 3:19 - trees will have some specific order that
• 3:21 - is intended to sort of make using them
• 3:23 - easier it's one of the reasons why
• 3:25 - people like using trees so much is once
• 3:27 - you have them a specific order and
• 3:29 - they're balanced you have this guarantee
• 3:31 - that you'll only look at log of n items
• 3:34 - to find what you're looking for where n
• 3:36 - is the total number of items in this
• 3:38 - tree so in this case we've got about 15
• 3:40 - 16 items and you know as we go down
• 3:43 - through it what most have to look at
• 3:45 - four different items to find what we're
• 3:46 - looking for so i'm going to show you why
• 3:48 - what the order of this is you can see
• 3:51 - here in the bottom after we've got a 1
• 3:52 - then we move up to a 2 and we've got a
• 3:54 - three and then we can go up here to this
• 3:56 - for and this entire tree is sorted from
• 3:59 - lowest item to highest item the way it
• 4:02 - sorted is that at every single node for
• 4:05 - example this eight node everything
• 4:07 - stored to the left of that node is
• 4:08 - smaller than it or less than it and
• 4:11 - everything's stored to the right of that
• 4:12 - node is greater than it so in this case
• 4:15 - you can see everything over here is
• 4:16 - greater than an eight and everything
• 4:18 - over here is less than an eight
• 4:19 - similarly if we look at the for
• 4:21 - everything to the left of it is less
• 4:23 - than it and everything the right of it
• 4:25 - is greater than a four so this holds
• 4:28 - true throughout the entire tree and what
• 4:30 - this ends up doing is when we're
• 4:31 - looking for numbers we can actually go
• 4:33 - through and just decide which direction
• 4:34 - to go at any point in time really easily
• 4:36 - because we know exactly what to expect
• 4:38 - so we're at this aight we can actually
• 4:41 - say well if we need a number let's say
• 4:43 - we're trying to find a seven we can say
• 4:44 - all right well i know 7 is less than an
• 4:46 - eight so it has to be on the left hand
• 4:47 - side of its here so we'll go down to the
• 4:50 - four and while we're looking at the
• 4:52 - floor will say alright well i'm looking
• 4:54 - for a seven it's greater than a four so
• 4:55 - we need to go right so we go down to the
• 4:58 - six and again the same exact thing we're
• 5:00 - looking for a seven we know that's
• 5:02 - greater than a 60 we have to go right
• 5:03 - and then here we get to the seven now if
• 5:06 - this wasn't a seven say this was like a
• 5:08 - 6.5 at this point we could look and say
• 5:11 - alright what we need to go right but you
• 5:13 - know since there's no children to the
• 5:14 - right we could say a seven isn't in this
• 5:16 - tree but since we found it we you know
• 5:18 - we know we only had to look at a couple
• 5:20 - different spots to find it in this case
• 5:21 - it was one two three four so if you look
• 5:24 - at the log of 15 base to at least it is
• 5:27 - going to give you 4 so 4 is the most
• 5:30 - number of things you're ever going to
• 5:31 - have to look at in this case and that's
• 5:34 - new it's because it's a nice balanced
• 5:35 - tree and it sorted