Depth First Search (DFS) on a Binary Tree

In this video we cover how the depth first search algorithm works. We do so by starting with a binary tree and walking through how the algorithm would iterate over the tree searching for a specific node.

We intentionally start with a tree because this removes a lot of complicating factors that might be present in other graphs, such as running into a cycle, but everything you learn here will be applicable to when we start working with cyclical graphs to also run our DFS.

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? Representing Binary Trees in Go Code

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 - I
• 0:01 - the first algorithm we're going to talk
• 0:04 - about is the depth-first search now the
• 0:06 - depth-first search and the breadth first
• 0:08 - search are both similar in a lot of ways
• 0:11 - but we're just going to go over one of
• 0:13 - them first and then as we go to the
• 0:14 - breadth first search you'll see how the
• 0:16 - two sort of relate to each other and how
• 0:17 - they're similar so in general a DFS and
• 0:23 - a BFS which are short for depth first
• 0:25 - search and breadth first search can be
• 0:28 - used to answer questions like can I get
• 0:30 - from node a two node be in our graph so
• 0:33 - if you're looking at this year graph you
• 0:35 - might ask can I get from the 8th to be 7
• 0:38 - now in a fully connected graph like most
• 0:42 - trees all the nodes are connected so
• 0:46 - what this means is that you don't really
• 0:48 - have to say can I get from the 8th to
• 0:49 - the seven instead you can kind of just
• 0:51 - say you know is the seven in our graph
• 0:54 - because you know you're always going to
• 0:56 - start from the root and it's always
• 0:57 - connected to everything but it's
• 0:59 - important to you show the difference
• 1:00 - that if this line didn't exist we can't
• 1:03 - just say does 12 exist in our graph
• 1:05 - because we start at the eight we won't
• 1:07 - ever hit the 12 but it does exist in our
• 1:09 - entire graph so that's a very important
• 1:11 - difference that if you have a fully
• 1:13 - connected graph where all these things
• 1:15 - are connected to each other you can just
• 1:16 - say does it exist in our graph and trees
• 1:18 - generally tend to be fully connected
• 1:20 - I've never really seen a useful tree
• 1:22 - that's not so you know moving forward
• 1:24 - we're going to assume that our trees are
• 1:26 - completely connected but when we start
• 1:28 - to look at graphs that aren't all is
• 1:29 - that you have to remember that you
• 1:31 - sometimes that's something you have to
• 1:32 - remember
• 1:35 - so we're going to go ahead with the
• 1:37 - example does seven exist in our graph so
• 1:42 - we're going to always start at this root
• 1:43 - note of eight and we're going to
• 1:44 - basically look for seven inside of our
• 1:46 - graph now this graph happens to be
• 1:48 - sorted but we're going to pretend like
• 1:50 - we don't know that we're just going to
• 1:51 - pretend like we're just doing a search
• 1:52 - in our graph and we don't really know
• 1:54 - how the data is organized
• 1:56 - so a DFS is called a depth-first search
• 1:59 - because it goes as deep as possible and
• 2:01 - then it back tracks and continues to go
• 2:03 - as deep as possible every time I can
• 2:05 - that's new i gets the term depth-first
• 2:07 - search so i'm just going to sort of walk
• 2:11 - you through how this might go about with
• 2:13 - a you know with a search we always start
• 2:15 - at our root node so that's our eight
• 2:16 - here and while we're there we're going
• 2:19 - to basically in this case we're always
• 2:22 - going to go left as soon as we can and
• 2:24 - if we can't go left any farther we're
• 2:25 - going to backtrack and then we're going
• 2:26 - to try to go right as far as we can or
• 2:29 - sorry I take that back we're always
• 2:30 - going to go left as far as we can and
• 2:32 - then if we can't go left we're going to
• 2:33 - go right and if we can't go right we're
• 2:35 - going to backtrack so starting at the
• 2:37 - eighth we're going to go left so left
• 2:40 - would take us to this for here so once
• 2:44 - we get to the four we're going to we
• 2:46 - will check along the way to see if we
• 2:47 - found the seven we're looking for and
• 2:48 - four is not seven so again we're going
• 2:50 - to go left so we find a two here and we
• 2:53 - realize that too is not the number we're
• 2:55 - looking for so again we're going to go
• 2:56 - left so at this point we get to the one
• 2:59 - it's not the number we're looking for
• 3:01 - and we try to go left but there's
• 3:03 - nowhere to go to the left we don't
• 3:04 - really have a left child so instead of
• 3:07 - going left we then go to the next step
• 3:08 - and we look at our right child so one
• 3:10 - doesn't have a right child either so at
• 3:13 - this point it's tried to go left its
• 3:14 - tried to go right so now we're going to
• 3:16 - backtrack up to the two so once we
• 3:20 - backtrack the two is going to continue
• 3:21 - from where ever it left off so the last
• 3:23 - thing the two did was it tried to go
• 3:25 - left and it went to the one so at this
• 3:27 - point it's know it's going to know that
• 3:28 - it can't go left anymore and it's going
• 3:30 - to try to go right so we get down to the
• 3:32 - three and we do the exact same thing we
• 3:35 - are talking about before where we try to
• 3:36 - go left there are no children we try to
• 3:39 - go right there are no children so then
• 3:41 - we're going to backtrack so this time
• 3:42 - we're going to backtrack to the two and
• 3:44 - then the two is not going to have any
• 3:45 - word you it's not going to have a left
• 3:47 - or right to go to because we've already
• 3:48 - been to both so the two will backtrack
• 3:50 - to the four finally when we get to the
• 3:52 - for the four is going to backtrack or
• 3:55 - sorry the four is going to know that we
• 3:57 - already searched the left hand side so
• 3:59 - it's now going to go to the right side
• 4:00 - so that's how it got to the six here is
• 4:02 - we backtracked all the way to the four
• 4:04 - then we went down to the six
• 4:07 - so once we're at the six we continue
• 4:09 - with our normal flow we we go left first
• 4:11 - we get to the five and wilmer at the
• 4:14 - five if we try to go left we try to go
• 4:16 - right we can't do either so then we're
• 4:17 - going to backtrack back up to the six
• 4:19 - and then once we get back to the six
• 4:21 - we're going now we're going to go down
• 4:22 - the right path so we go down this right
• 4:24 - path here and you notice that this is
• 4:26 - the number we're looking for this is our
• 4:28 - seven so we have successfully found
• 4:30 - seven using a DFS so the big thing to
• 4:34 - remember is that when you're running the
• 4:35 - DFS you always go left first and then if
• 4:38 - you once you're done going left as much
• 4:40 - as you can you then go right and then if
• 4:44 - you done going all the right directions
• 4:45 - you can you backtrack so the way you
• 4:48 - would sort of find out if seven doesn't
• 4:50 - exist in this graph is if you ever got
• 4:51 - to the very root note the eight and it
• 4:53 - back tracks and there's nothing else to
• 4:55 - do that would mean that at that point we
• 4:57 - have not found we were looking for and
• 4:59 - it's not in our graph but when you're at
• 5:01 - the four for example you could go the
• 5:03 - entire way down the left the entire way
• 5:05 - down the right and say we are looking
• 5:06 - for the number 9 over here at this point
• 5:10 - we would backtrack to the eight and then
• 5:12 - from the eight we would have to go down
• 5:13 - this right hand side path and we'd have
• 5:14 - to look at all these nodes before we
• 5:16 - could actually say that nine doesn't
• 5:18 - exist in our graph so that's how the DFS
• 5:20 - works you're always going as deep as
• 5:22 - possible down a path backtracking as
• 5:24 - little as you can and then going down
• 5:25 - another deep route and you keep doing
• 5:27 - this until you find what you're looking
• 5:28 - for or you've looked at the entire graph
• 5:30 - so I'm just going to quickly walk
• 5:33 - through this with you one last time I
• 5:35 - just want to show you you know basically
• 5:37 - what all nodes we'd look at along the
• 5:39 - way if we were searching for something
• 5:42 - that does not exist in our graph so
• 5:43 - let's say we're searching for the number
• 5:45 - 16 and it doesn't exist so the first
• 5:47 - thing we do is look at this eight then
• 5:49 - we'd go left to the four left to the two
• 5:52 - left to the one so there's no children
• 5:54 - to go to so we backtrack back up to the
• 5:56 - two so now we're going to go down to the
• 5:58 - right hand side so we go to the three
• 6:00 - again there's no children so we
• 6:01 - backtrack up to the two there's no right
• 6:04 - or left path to go down anymore so we go
• 6:06 - back up to the fore and at this time
• 6:07 - we're going to go down the right side so
• 6:09 - we go to the six the five backtrack up
• 6:12 - to the six down to the seven backtrack
• 6:16 - to the six backtrack to the four
• 6:18 - backtrack to the eight now we can go
• 6:20 - down the right
• 6:21 - hand side so we go 12 and now we're
• 6:23 - going down the left-hand side so we go
• 6:25 - 10 9 we haven't found the 16 we're
• 6:29 - looking for so we backtrack we get on
• 6:32 - the right side we get to 11 not the 16
• 6:34 - we're looking for so we backtrack to the
• 6:36 - 10 backtrack to the 12 and we go down to
• 6:39 - 14 and then we go to the 13 we don't
• 6:42 - find what we're looking for so we
• 6:43 - backtrack to the 14 go down the
• 6:45 - right-hand side don't file we're looking
• 6:47 - for so at this point we backtrack to the
• 6:49 - 14 backtrack to the 12 backtrack to the
• 6:53 - eighth and at this point we're at the
• 6:54 - eighth there's nowhere else to go so we
• 6:56 - backtrack but there's nowhere to
• 6:58 - backtrack to either because we're at the
• 6:59 - root node so that's how we know that 16
• 7:02 - does not exist in this graph if you're
• 7:06 - enjoying this series I'd really
• 7:07 - appreciate it if you could head over to
• 7:09 - my blog at Calhoun do and head down to
• 7:12 - the mailing list and sign up so I won't
• 7:15 - spam you or do anything like that when
• 7:17 - you sign up for the mailing list i will
• 7:19 - send you a free sample from my book web
• 7:21 - development with go and then i'll send
• 7:23 - you an email about once a week just
• 7:25 - letting you know about new articles or
• 7:26 - new videos or really any new free
• 7:28 - content that i'm sending our that i'm
• 7:30 - releasing publishing and i'll also let
• 7:32 - you know about you know what i'm working
• 7:34 - on in the coming weeks and try to get
• 7:35 - some feedback on what everybody thinks i
• 7:37 - should focus on and what they'd like to
• 7:38 - hear me talk about and every once in a
• 7:41 - while when I release a new product a new
• 7:43 - course or in a book or something like
• 7:45 - that I will send an email to the mailing
• 7:46 - list often times it'll be accompanied
• 7:48 - with a free sample or a discount code or
• 7:50 - something like that basically just
• 7:52 - letting you know about it and if you
• 7:53 - like the stuff that I'm writing chances
• 7:55 - are you'll you know at least appreciate
• 7:57 - some of that and I definitely really
• 7:59 - appreciate any of the purchases because
• 8:00 - they help support me and help me a lot
• 8:02 - to keep creating free material like this
• 8:03 - thanks so much