Coding Interview Fundamentals: DFS and Recursion for Binary Trees

[00:01] former LinkedIn software engineer who has spent the last three years helping in this video I'm going to be talking about depth for search and recursion for search and recursion to solve

[00:14] questions related to Binary trees now when it comes to the coding interview arguably the two most important topics out there and that's because they're very versatile aside from binary trees

[00:26] they can also be used to solve questions involving graphs backtracking and dynamic programming so this video is intended for anyone who's maybe just or for those who are comfortable tackling questions in that easy to

[00:40] medium range but really just want to build a strong foundation so that they have more confidence solving problems moving forward so we're going to first touch on how to use depth first search to to Traverse the nodes in a binary

[00:52] tree but the main focus of this video will be about recursion and how to use recursion to solve binary tree questions so so we'll learn about the relationship between death for search and recursion we'll learn about how to think

[01:05] recursively when solving binary tree problems and finally we'll learn how to take that thinking and translate that into a working recursive implementation so there is a text version of this material at the hello interview website

[01:18] I'm going to leave all links in the description below there you'll find free interactive visual guides to the most important coding interview patterns and links to practice problems that you can try try for yourself to apply what you

[01:31] learned in this video lastly before we get started please don't hesitate to like comment and subscribe especially if you want to see more of this material in you want to see more of this material in the future all right so let's get

[01:47] algorithm for visiting every node in a tree or graph like data structure it does so in a very specific fashion which is what we're going to visualize now so depth for search is going to start at the root node of our binary tree

[02:00] then it's going to visit nodes by going down and to the left until we reach a leaf node which is a dead end now at this Leaf node since we can't go down we're going to backtrack back up to the previous node so this backtracking is a

[02:15] key part of the depth first search algorithm and it ensures that we can visit every node in our binary tree but I also want to point out another fact is that when we backtrack away from a node in our binary tree we've actually

[02:29] explored all of the nodes in the sub tree rooted at that node so we've explored all of the nodes at the subtree rooted at one when we backtracked away from it and went back to Noe two and this fact plays a key role when we solve

[02:42] questions using recursion as we're going to see in a little bit but from now we can continue the depth for search process so at node two we're going to now visit node 3 node three we reached a dead end so we're going to backtrack

[02:54] back up to node two at node two we finished visiting both of its left and right children children so we're going to backtrack back up to node 4 and notice how after we've done that backtracking we've finished visiting all

[03:07] of the nodes in this left subtree which I've just shown by putting those nodes in dark blue so at node four we're just going to now move on to the right and here we' reached a leaf node so we're going to backtrack backtrack

[03:22] and when we finally reached node 4 again which is our root we've now visited every single node in our binary tree and our depth for search Al has finished so we can think of depth for search as a form of iteration and we can use

[03:36] iteration to solve a question like finding the sum of the nodes in a binary tree so what we'll do is we'll keep a running counter right here sum and then over every single node in the binary tree and when we reach a node we're

[03:51] going to add that node's value to the sum and when the depth first search eventually finishes and visits every single node we're going to have the sum of our binary tree at the end so I'm going to refer to this approach as the

[04:04] pure DFS approach to finding the sum of a binary tree it works perfectly fine there's nothing wrong with it but now I want to shift gears a little bit and talk about the recursive approach to the same question we'll dig into why and the

[04:18] advantages of the recursive approach in just a little bit but first we're going to talk about the how so to solve this question of finding the sum of of the nodes in a binary tree using recursion we're going to need a

[04:33] to look like this we're going to pick a node in our binary tree let's just pick the root node for now and we're going to think in terms of this node's left and right sub trees so here's the left sub

[04:46] tree and here's the right sub tree if we know the sum of the left sub tree 2 + 3 + 1 which is 6 and we know the sum of the right sub tree 7 + 5 which is 12 well we can use those two values we can add them together plus the sum of our

[05:02] own node which is four we can add them all together to get 22 which is the sum of this entire binary tree now the nice thing about describing the sum of a tree like this is that it can be applied to any sub tree in our binary tree so if we

[05:18] look at this left sub tree right here we're going to pick this node two as the root its left sub tree has some one Its Right sub tree has some three now 1 + 3 + 2 is going to give us six which then in turn can be used to find the sum of

[05:34] the entire sub tree like we just saw same thing with this sub tree right here its left sub tree has sum zero right sub tree has sum five 5 + 7 + 0 is going to

[05:47] give us 12 which again is part of the sum of the entire sub tree so if I were to write an equation to describe what we just saw it would look something like this sum of a node equal to sum of its letter left sub tree plus the sum of its

[06:02] right sub tree plus the value of its node sum node just represents the sum of any sub tree rooted at a particular node equal to the sum of its left sub tree plus the sum of its right sub tree plus the value of its node itself so the one

[06:18] thing we do have to be careful of when we're using this equation is that for an empty sub tree like the one right here this actually won't apply this is because an empty sub tree has no left and right subt trees so we can't

[06:32] actually use this equation to find its sum an empty sub tree is the base case for our recursion meaning we can calculat its sum directly and this is because we know that an empty sub tree has a sum of zero because it has no

[06:44] nodes so these two equations can be used to find the sum of any sub Tree in a binary tree so now let's actually visualize how the recursive solution to this problem Works in code this is also going to allow us to make the connection

[06:58] between our recursive solution and the depth for search process that we covered in the beginning of this video so on our left here we have the recursive solution to our problem let's just take a moment to understand what this function

[07:11] represents We have tree suum takes in a value node and what it's going to return is the sum of the sub tree rooted at the given node okay and it's going to do that recursively the first two lines represent the base case the sum of an

[07:24] empty sub tree is zero while these three lines represent the recursive way of right sub trees so now we're going to visualize each step of how this recursive function works so initially it's called with node 4 and when this

[07:39] function eventually returns it's going to return with 22 as the sum of this entire tree right here so the first step of this function is to say okay in order to find the sum of my tree I need to

[07:52] first know the sum of my left sub tree so we're going to do that by going in and making a recursive call to tree Su on . left so when we make that recursive call what we're doing is we're taking a copy of the recursive function and we're

[08:06] shown right here so it's important to note that when this function eventually returns it's going to return with the sum of this sub tree which is six so in order to find the sum of this sub tree we need to follow that same process we

[08:19] need to First find the sum of the left sub tree so we're going to do that by making a recursive call now node is equal to one in this case and if you equal to one in this case and if you notice this is just the DFS process that

[08:31] we were talked about in the very beginning of this video so here okay node one needs the sum of its left sub tree just going to make a recursive call to find that and here we've reached our first base case so now not is none so

[08:44] this is going to hit this base case right here so we can return zero directly it's really important to understand where this return value goes and what it represents so we're going to return zero now this value gets returned

[08:58] to the uh node one as the sum of node one's left subtree so we have that value right here and this was just the backtracking portion of DFS so now node one has this value of zero for its left sub tree so it's going to say okay let

[09:14] just going to do that by making a recursive call no is none here so we can return zero directly okay at this point node one has a sum of both of its left and right subt trees so we going to take those two values add it to its own value

[09:29] those two values add it to its own value and return it back to node two okay so 0 and return it back to node two okay so 0 + 0 + 1 the sum of this sub tree is 1 now node two receives that value as a sum of its left sub tree and now it's

[09:41] going to go on and make a recursive call to find the sum of its right sub tree okay this just looks a lot like what we just covered hitting the base case hitting the base case okay so now

[09:55] right sub trees which is zero it's going to take Z +0 add it to to take Z +0 add it to three okay so now that three gets returned in the backtracking step to node two node two now has the sum of its

[10:10] left and right sub trees one and three so it's going to take one and three add it to its own value and return that back up to its parent which is node four so remember how I said when DFS backtracks away from a node it means we finished

[10:25] tree rooted at that node and so here's just a a perfect place to visualize how that is important for the recursive solution at this point we've backtracked away from node two which means we

[10:38] finished visiting all of the nodes in this subtree which also means we have the sum of that subtree so that sum is the value that we backtrack with back up to Route node 4 while the rest of the animation plays out let's just recap the

[10:52] connection between DFS and recursion so we use recursion to describe the sum of a binary tree in terms of its left and right subt trees and DFS just controls the order in which we visit those subt trees to supply the relevant sums and

[11:06] before we move on let's just talk about the time and space complexity of this function the time complexity is going to be o of n where n is the number of nodes in our binary tree and that's because we visit every single node once and in each

[11:20] node we're doing a constant amount of work now when we talk about the space complexity this visual is actually going to help us understand that as well the to help us understand that as well the space complex city is O of H where H is

[11:32] the height of the binary tree and if we want to visualize what that looks like execution you'll notice that there are a total of four calls on the call stack we have to account for the space that each of these calls takes on the call stack

[11:46] and that just corresponds to the height of this binary tree right here the four nodes that we have starting from the route down to this node right here so recursion when solving binary tree

[11:59] problems in general there are two advantages for using recursion the first is that it lets us solve a specific type of problem much more naturally and easier than other approaches we're going to cover what those problems are in the

[12:12] next video so don't forget to subscribe if you don't want to miss out on that but the second reason is really for ease of implementation on the left we have the recursive approach to our treesome problem and on our right we have two

[12:26] different versions of the pure DFS uh approach to the treesome problem that we case the recursive version is just much fewer lines of code in this version we're using recursion to implement DFS but we have to introduce a global

[12:40] variable to repeatedly add to it in each call in this version we're using an iterative version of DFS it's going to be beyond the scope of the video so I don't want to get too much into it but this avoids having to use that Global

[12:52] variable but we are writing a lot more lines of code and so aside from this brevity once we' figured out how to think recursively about a binary tree straightforward process that we can take to go from that recursive way of

[13:07] the actual implementation we're going to cover that we're going to write a recursive solution to counting the number of nodes in a binary tree and we're going to do that by following the five steps that we

[13:22] with how to think about the problem recursively then how to take that thinking and turn that into a working recursive solution so let's just look at this binary tree right here so we're thinking recursively what I like to do

[13:36] is I like to pick a note in the tree and then ask myself okay what do I need from solve my problem remember I'm trying to count the number of nodes in this tree okay so if I know that there are three nodes in my left sub tree 1 2 3 and I

[13:50] know that there are two nodes in my right sub tree well I can just take those two values and add one for my node to get 1 + 2 + three for a total of

[14:06] return the number of nodes in the subtree rooted at the given node so it returns number of nodes in the subtree rooted at node and having this clear definition of what each function call is

[14:18] going to return is important because it allows us to specify the base case correctly which is step three so our base case okay if each call returns a number of nodes in the sub tree we did node if node is empty so if not node

[14:32] then we just want to return we want to return zero because there are no nodes in an empty sub tree okay so after that's done we can actually move on to making the recursive calls so this is step four so I'm going to make recursive

[14:44] calls to node. left and no do right and then I'm going to use those values in the return statement based on the way that we broke things down in step one so we can return left plus

[14:58] right + 1 one now I just want to use the same process to show how to write a recursive solution to a slightly more complicated question in this question I'm writing a recursive solution to check if a Target

[15:12] exists within a given binary tree so if I have this binary Tre right here and my target is two then that's going to return true because two is right here but if I was searching for the Target eight I would return false so again just

[15:26] going to use these five steps to go from the way that I think about this problem recursively to the actual implementation okay so first step is to think recursively again I'm going to pick a node then ask myself what do I need from

[15:40] my left and right subt trees in order to solve my problem well for this problem I'm going to need to know if the target exists in my left or right sub trees because if either of those things are true then that means the target exists

[15:55] in my entire binary tree right if two exists in this left sub tree that means two exists in this entire tree so once I've made that observation I can clearly Define what each function is going to

[16:07] return so I'm just going to write that here returns if the target exists in the here returns if the target exists in the sub tree rooted at the given node again having a clear definition is really going to help keep my base case correct

[16:22] my base case I'm thinking empty tree so if node is none I'm going to return if node is none I'm going to return false because a Target cannot exist in a empty tree but based So based on this definition we also need some more

[16:36] information that we can't just get through the recursive calls so let's say we're searching for the Target four in this tree and we're at this node well four doesn't exist in our left sub tree four doesn't exist in our right sub tree

[16:48] so those recursive calls would return false but our node is actually equal to the Target so we also need to check if our node is equal to the Target then we can just return true right away so I'm going to do that now in the

[17:06] relation to the recursive calls is really important and we're going to see why in the next section for now I'm just going to finish writing this function so if I know that my node doesn't equal the Target that means I need to check my

[17:20] left and right sub trees so I can move on to step four and five making the recursive calls and using them in the return statement and for this particular them together in the return statement for something like this so we can return

[17:33] if the search Target exists in the left sube or the search Target exists in the right sub tree so the last thing I want to do is just visualize how this function works for a few different cases when our

[17:49] Target exists within the binary tree and the reason for this is I'm just going to show something called early return so here I've just written the same logic as we had before in just a slightly different way that makes it easier to

[18:02] tell exactly what is returning true okay so for the first example let's just look at the most trivial one when we're searching for this target four and it exists at the root of our binary tree so in this case node. Val is going to equal

[18:14] to our Target and we can just return true right away without having to make any recursive calls at all let's look at a slightly more interesting example which is when our Target exists in our left sub tree when we're searching for

[18:28] the Target one okay so let's see what happens so first thing to check no do vals equal to Target that's not true so we need to go searching our left sub Tree by making a recursive call now node is equal to two

[18:44] within this sub tree so again we're going to make that recursive call because 2 is not equal to four sorry two is not equal to one so we're going to make that recursive call to our left sub tree so at this point we're searching

[18:56] for if the target one exists with in this sub tree right here so we're going to see that node. Val is equal to Target so we can just return true so this True Value gets received by the parent of node one which is node two and it just

[19:10] indicates that hey that that Target one exists somewhere in node twos left subtree so this going to evaluate to true so now we can return true directly without having to explore any parts of the right sub tree which is what this

[19:25] code is doing so we're going to see we're going to skip this this recursive call and just return true directly so we return true to our parent so what we did is when we were right there we basically said okay our Target

[19:39] exists in my left sub tree so I don't even need to check anything in my right sub tree and you can imagine that if there are a lot of nodes coming out here in that right sub tree then this would be a very useful optimization that we

[19:51] could make now the root node originally which is node four it received this which is node four it received this value as true so it can just return true saying that we found one somewhere in this binary tree so this is going to be

[20:03] it for this video and we've covered a lot we've covered the basics of depth for search we've covered how to approach using recursion to solve binary tree problems and we've learned how to take that recursive approach and translate

[20:17] that directly into code we've also visualized how recursive functions work and how that they can do things such as early returns and recursion is always with it because there's so much happening behind the scenes but

[20:30] hopefully this video helped spell exactly what each of those steps are and you'll just get more and more familiar with them as you practice so the most important thing after watching this video is to make sure you tackle some

[20:43] problems on your own I've left the links to the relevant questions on hello interview.com in the description below each of these questions is going to have detailed solutions that use a lot of visuals and follow the same step-by-step

[20:56] video so by practice practicing doing them you'll make sure you get the repetition that you need to really really understand these Concepts and if you like this video be sure to subscribe so you don't miss out on the next one in

[21:09] which we further our understanding of recursion when it comes to Binary trees by talking about when to use helper functions when to use Global variables and the types of questions that are best solved by using recursion okay so I hope

[21:22] this helps everybody in their Journey good luck on your interviews and I'll good luck on your interviews and I'll see you next time