Coding Interview Fundamentals: Post-Order Traversal

[00:02] spent the last three years helping others prepare for the coding interview in this video we're going to break down the post-order traversal which is really the most important Technique we need to know when we're solving binary tree

[00:16] questions using recursion so we're going to start by looking at a classic interview question that's going to teach us the motivation for the technique then we're going to look at how it can be applied to three additional questions

[00:28] including a hard question that is frequently asked by all of the top tech please don't forget to like comment and subscribe and don't forget to check out the link in the description below for a free interactive visual guide to all of

[00:43] patterns so the first question we're going to look at is diameter of a binary tree we're first going to look at the Brute Force approach to the problem the post-order traversal approach is

[00:56] necessary this is a pretty well-known interview question so if you are already familiar with it feel free to skip ahead to the 10 minute 30 Mark where we talk about how the postorder approach can be used to solve problems in general in

[01:08] this question we are being asked to find the diameter of a binary tree where the diameter is defined as the longest path between any two nodes in the tree if we have this tree on the left then the diameter is going to be this path right

[01:21] here between nodes 5 and three and specifically we want the number of edges on this path which is going to be 1 2 three four five in this case the diameter of a tree does not have to go

[01:34] through the root for example in this tree right here the diameter is this tree right here the diameter is this path and it has a total of 1 2 3 4 5 6 7 edges so let's say we have this binary tree right here the diameter is this

[01:47] path between nodes four and three for a length of 1 2 3 4 5 the first thing we want to note is that the diameter of a binary tree is always going to exist between two Leaf nodes in the binary tree so our algorithm is going to look

[02:02] like this we're going to visit every single node in our binary tree and at each node we're going to calculate the length of the longest Leaf to Leaf path that runs through that node and after we finish visiting each node we can return

[02:14] the longest of those paths that we found so there are two ways to execute this algorithm the first is from the top down what this means is we're going to start by finding the longest path that runs through the root node now how do we do

[02:27] this well the longest path that runs through the root is just going to be equal to the height of the root node's left sub tree so this has 1 2 3 4 for height of four plus the height of the node's right sub tree which is one so

[02:44] once we have those two values we can add them two together to get the length of the longest path that runs through there which is going to be five so after we path running through the root node we're going to move on to the next node in the

[02:57] tree and do the same calculation here we're just going to follow that same process find the height of the left sub tree this is going to be one then we're sub tree which is three in this

[03:10] case we can add those two numbers to get four so we're going to do that same process for every single node in the binary tree and you might be able to tell that there's a lot of repeat work being done in particular at each node we

[03:25] have to Traverse all the nodes below it to find the height of the left the left and write sub trees now all that repeat work leads to a big O of n s runtime which is not going to be good enough for the coding interview so here's the code

[03:39] for this top down approach we have this function diameter right here which takes in a node and the first thing this function does is it gets the height of nodes left and right subt trees using this recursive function here after those

[03:51] the longest path through the root of this sub Tree by adding left height and right height together and after that it moves on to finding the longest path that runs through the no's left sub tree and so this is where that repeat work is

[04:04] coming from every time we recurse one node further down to get its longest path we have to find the height of that node's left and right subt trees so you can kind of think of this as a nested for Loop of sorts and again this is this

[04:18] has the bigo of n^2 runtime so now let's look at the bottom up approach to this problem instead of starting at our root node we're instead going to want to think about starting at the bottommost node in our tree which is this node

[04:32] right here and when we're at this node we want to do the same thing we did before we want to calculate the length of the longest path that runs through this node using the heights of its left and right sub trees so this node has

[04:45] empty left and right sub trees so they're both going to have height zero and now node three can take those two values add them together to get the length of the longest path which is zero so let's just write that value down here

[04:59] in a VAR called Max we'll talk about this variable a little bit more when we bottomup approach in a second but for now let's keep on going on with the process so after node 3 is done finding its longest path it's going to return

[05:14] its height to its parent node and that height is one and after it returns that height we're done with it we don't ever need to visit this node again and now node one has part of what it needs to calculate its own longest path it also

[05:30] needs the height of its right sub tree So eventually this node will pass in its one we're done with this node now node one has the height of both its left and right sub trees so it's going to add them two together and to get two which

[05:45] is just this path right here okay so now the max path that we found so far is two so we're going to update that and this is just saying thus far after all of the nodes that we visited which are the nodes in this subtree we have found a

[05:58] maximum path of length two so now node one is done calculating its longest path it's going to return its height back up to its parent which is going to be two we're done with these entire nodes this is going to return a one so now we're

[06:12] going to add these two together 2 + 1 which is three update our Max now we're going to return our height to our parent so this is going to return a three we're done with these nodes this returns a one okay and then we're going to take those

[06:27] which is four and since we're at our root we visited every single node and we can return that our diameter is four so this bottom up approach is the optimal solution to this question because we visit each node in

[06:42] our binary tree Once the runtime for this algorithm is going to be Big O of n where n is the number of nodes in our binary tree so here's the code for optimal solution we'll see that we have a single recursive function that Returns

[06:56] the height of the sub tree rooted at a given node it also calculates the length of the longest path that runs through that node using the values of the heights of its left and right sub trees you can see that's being done right here

[07:09] and you notice that this calculation of left plus right is done after the there the fact that it's being done after the recursive calls is also known as a post-order traversal and it's what gives our algorithm bottom up behavior

[07:25] that we just saw so we're also using this Global variable Max right here to store the length of the longest path in our binary tree the reason why we want to use this Global variable is because our recursive function Returns the

[07:38] height of each sub tree and that's different than the value that our question is asking for and so by using a global variable to store the longest path that we've seen so far we're able to keep this return statement simple and

[07:53] to tell what the recursive function is doing and you can see that we don't return the result of the recursive function at the end we just return the value stored in Max after the recursive function has finished executing so now

[08:08] let's visualize a few steps of this algorithm so we can just get a complete understanding of how everything works so the first step is to initialize that Global variable Max now we're going to start our recursive function at the root

[08:20] of this binary tree now this recursive function is trying to calculate both the longest path that runs through the root node and the height of its sub tree to its left sub tree so we're going to recurse left sub tree

[08:37] recurse so now we've reached our first base case where node is none so we're going to return zero to its parent so now node one has the height of its left sub tree it's going to get the height of its right sub tree which is zero so now

[08:51] at this point node one has received the height of both its left and right sub trees so now it can calculate the length of the longest path path that runs it's going to do left plus right which

[09:04] is still zero so max is still zero we haven't found a longer path than zero going to return the height of our sub tree back up to our parent okay so now of its left sub tree it's going to move

[09:18] sub tree which is going to go through a few base cases like we just few base cases like we just saw okay right here this is a base case so now like before Noe four has the height of its left and right sub trees

[09:31] add some together now it's going to return one to its parent so now node 9 trees it's going to add them two together to get two and it's going to

[09:43] update the variable Max right here so max is updated this just means we found a path of length to so far in this subtree which is all the nodes that we visited so far and now we're going to return our height to our parent which is

[09:57] Max left plus right plus 1 which is two okay so this just continues until we visited every single node in the binary tree let's just go over the complexities one more time the time complexity of this algorithm is going to be Big O of n

[10:11] because we only visit every single node once and the space complexity is going to be o of H and this is just due to the nature of depth for search which means we'll have as many of these call frames on the call stack as there are nodes in

[10:25] the height of our binary tree now let's summarize what we just covered there are problem the first is the top down approach which has Big O of N squ Run time which is not good enough for the coding interview the other approach is

[10:38] from the bottom up here we think about first calculating the longest path that runs through the leaf nodes of the tree the leaf nodes then return their heights up to the parent which then use those values to calculate its longest path and

[10:52] we work our way up the tree only visiting each node once and that results in the optimal bigo of n run time now this bottom up approach is also known as a post-order traversal and that's going to be the focus of this

[11:06] video from here on out so when do we need to use this postorder traversal so whenever we need to calculate something at each node in a binary tree using values from that node's left and right sub tree we're going to need to use this

[11:21] post-order traversal in order for us to get the optimal solution so in our diameter example at each node we needed the heights of the left and right subtree in order to calculate the length of the longest path that runs through

[11:35] each node and if you notice in the code we're calculating the length of the longest path through each node after the recursive calls to its left and right subt trees have finished and that's what gives the postorder traversal its name

[11:47] we're processing the current node after its left and right subt trees let's now look at another example of a question that uses this post-order traversal so find the tilt of a binary tree this question is rated as an easy only code

[12:01] so it might be something you see in the earlier rounds of your interview like doing a phone screen for example but regardless it's a great question for us to start plying the concepts we just learned about the post-order traversal

[12:13] so here we're given a binary tree and we're asked to find its tilt now the Tilt is something that can be calculated at each node and it's defined as the difference between each node's left sub tree and right sub tree sum so in this

[12:27] case the Tilt here at this node is going to be 9 - 2 we want to take the absolute value of that so at this node it's going to be seven and these have empty left and right sub trees so these are going to be zero and zero okay and the Tilt

[12:41] applies to every node in a binary tree so in this case this is one this is four so the Tilt at this node is going to be three uh the Tilt at this node is going to be 7 - 3 which is 4 and then in order to calculate the Tilt at the root node

[12:55] we have to sum everything up here so this is going to be 14 this is going to this is going to be 14 this is going to be 12 okay so 14 - 12 is 2 so we want to sum up all of these numbers together so 3 + 4 + 2 so the tilt of this entire

[13:08] binary tree is going to be nine first thing what makes this a good question for using that postorder or bottomup approach it's because at each node we need to calculate something based on the values of our left and right sub trees

[13:21] in particular we need to know the sum of our left and right sub trees in order to calculate the Tilt at that node and now when we actually work through how to the bottom up so we're going to calculate the Tilt at this node first

[13:36] well it's left and right sub trees have sums of 0er so 0- 0 is 0 so at this note the Tilt is zero and we can store that in this variable here now when that's done what do we need to return to its parent to our parent so it can calculate

[13:51] its tilt well we need to return the sum of this entire sub tree so this is going to return a one same thing okay now we're going to move to 4 0 Z here tilt sum of its sub tree to its parent which is going to be four now when node 9 has

[14:05] those two values it's going to subtract them in order to find the Tilt at node 9 okay so 4 - 1 is three we're going to update this value right here now what do we need to return to its parent we need to return the sum of this entire subtree

[14:19] so that's going to be 1 + 4 + 9 which is 14 and that's going to continue in depth for search fashion until we visited every single node and we can have the Tilt for the entire tree and again this bottom up approach is going to let us do

[14:34] this in Big O of end time because we only have to visit each node in our binary tree Once so I'm going to leave the implementation up to you I left a link to this question on hello interview.com where you can practice it

[14:47] it's going to look a lot like the solution to diameter of a binary tree again it's just a really good question to get more comfortable with this postorder traversal so now on to to question number two so in this question

[15:01] we are being asked to find the longest univ Valley path in a binary tree and that is just a path where all of the nodes along that path have the same value so in this case this is one uni value path between nodes two and two but

[15:16] valy path right here because all nodes along this path have the same value three and what we really want is the number of edges along that path so this is going to return three in this case and just like the diameter of a binary

[15:30] tree question this longest path does not have to pass through the root of our binary tree so our approach to this problem is going to be very similar to the one that we Ed to find the diameter of a binary tree so let's quickly

[15:43] understand what each value that each node gets from its left and right subt trees and how that contributes to finding the longest path so in the diameter question each node returned the height of its sub tree to its parent so

[15:57] this node is going to return A2 to its parent while this node returns A1 and let's really understand what this value two represents here so from node 3's perspective this value two represents the longest path from its left sub tree

[16:12] the longest path from its left sub tree that node three can extend as part of the longest path that runs through node 3 and how does it extend that path it extends it by combining the longest path from the right subtree okay so if this

[16:25] two just indicates this path right here and when we we calculate the longest path that's going through node 3 we want to extend that by combining it with this path and that gives us the longest path that's running through node 3 so we can

[16:40] visualize it as basically gluing the longest paths from the left and right subt trees together in order to get the longest path that goes through no so understanding each return value as the longest path that can be extended by its

[16:54] parent is really the key to solving these longest path binary tree problems so so now let's look at how we can apply that same principle to this question of finding the longest uni valy path so our algorithm is going to work by visiting

[17:07] each node in our binary tree and at each node we're going to calculate the longest univ Valley path that runs through that node there are no univ valy nodes so at this node it's going to be this path and this node it's going to be

[17:20] this path and at the root it's actually this path right here and we want to take the longest of those paths for this path one 2 3 so let's visually understand how we're going to find each of those paths using the bottomup traversal and we're

[17:35] going to really focus on the return values that each sub tree returns to its parent which represents the longest path that can possibly be extended by its here because we're going to start at the bottom of the tree the longest path that

[17:50] can be extended by its parent actually has a length of zero and we'll find out exactly why in a second same with this node this is going to return a z so now now we're at node two we want to calculate the longest uni Valley path

[18:02] that runs through it using these two return values right here so the first thing we have to check is if we have to check if our node is equal to our left child because when that's true we're basically allowed to include this Edge

[18:16] right here as part of the longest Union Valley path and we're able to extend it using whatever value we got from our left child so in this case that's a zero so same logic applies to our right child they have the same value we can think

[18:32] about extending this Edge right here so for we one and so now the longest univ value path that goes through this node is going to be 1 + 0 + 1 + 0 which is going to be two so we're just going to store that value in this variable Max

[18:45] right here so now we're done with node two and we want to return a value up to our parent and we want to return the longest uni Val path that can possibly be extended by our parent okay we can't return this two here because

[18:59] uh our parent can't do anything with this path it only has to it can only exist from one side okay so the longest univ Val path that exists on one side is actually either of these could be this one or this one okay so it has a length

[19:13] of one so node 3 is a leaf node so it's also going to return a zero so now node also going to return a zero so now node 3 has received both of these values from its left and right sub trees and it needs to use them to calculate the

[19:26] length of the longest univ Val valy path that goes through it okay so first thing we have to check 3 is not equal to two so we actually can't use this value one at all it's not relevant because we can't include this Edge as part of

[19:41] extending our longest unit Valley path in this case 3 is equal to three so we can draw a one here now we're going to add that to our return value the fact that they're equal lets us use this return value so we're going to have a 1+

[19:55] 0 that just means the longest Union Valley path that goes go through this than our Max so we don't have to do anything now we have to return a value up to our parent we need to return the longest uh univ Valley path that can be

[20:10] extended to our parent okay and that's really just this path right here so we're going to return a one now this is a leaf node this is going to return a zero okay so our root node has to do the same thing has to use the same Val use

[20:22] these two values to calculate the longest Union Valley path that runs through it which is really just this path okay so first thing we have to other so we can think about drawing a one here this allows us to use our

[20:36] three are equal you can draw one here this allows us to use our return value so we're going to have 1 + 1+ 1 + 0 now our Max uni value path that we found so far has length three and now if we were

[20:51] to return a value to our parent let's say there are more nodes up here if we were then we would return two to indicate this path right here because again it can only be from one side so this would return A2 but since we are

[21:06] actually done visiting each node in our binary tree we can just return the value of Max okay so this is the approach to longest Union Valley path so really think about each node returning the length of the longest Union Valley path

[21:18] up to its parent that its parent can possibly extend the logic for this requires you to think about it in terms of how to implement it so I'm going to leave that to you there's a link to the description in hello interview.com as

[21:31] well where we can try it out so the last question we're going to look at is binary tree maximum path sum and this question is rated as a hard on leak code and it's asked by all of the top te companies such as meta Google Amazon

[21:46] Apple Etc okay and even though it's rated as hard it becomes a lot more manageable once we break it down in terms of what we already know about the way we learn to think about these longest path in a binary tree problem so

[22:00] this question is asking for the path in the binary tree with the maximum sum so in this case it's going to be this path right here between these two nodes for a right here between these two nodes for a sum of 3 + 2 + 1 + 3 for a total of nine

[22:14] and one thing to note is that this path can pass through any node in the binary tree but it must contain at least one node so we want to solve this in a very similar fashion to both the diameter and the longest Union Valley path questions

[22:27] that we already saw we want to solve this from the bottom up and we want each node to return the maximum value path that can be extended by its parent okay the binary tree and since we know that our path has to contain at least one

[22:43] value of this node as the maximum path that we've seen so far and now what we value of the maximum path that can be extended by its parent so this is going to return A3 this node is going to return A2 now when we're at node two

[22:57] longest path that goes through node two so that's going to be 3 + 2 + 2 for a total of seven so 7 is the longest path that we've seen so far and now we want to return the maximum value path that can be extended by our parent okay so

[23:12] that's actually going to be this path right here so that value is going to be the largest between 3 + 2 and 2+ 2 so that's going to be five okay and if we just visualize this this allows node one the root node to use this path as part

[23:28] of its maximum path sum that goes through it okay so now this one's going to return a three now node one has enough information to calculate the maximum path that runs through it which is 5 + 3 + 1 okay which is going to be 9

[23:43] and if we did have another value to return up we would return 3 + 5 + 1 as the maximum path that could be extended to its parent but we don't here so we can just return this nine at the very end so this is the gist of our approach

[23:57] about is how to handle negative values to figure that out I recommend playing around with a few small binary trees with negative values such as this one or this one just really think about what value each subtree needs to send to its

[24:12] parent so that its parent is able to accurately calculate its maximum path and again I'm going to leave that up to you it's a great way to practice your problem solving skills and get practice implementing this question using the

[24:26] bottom up and post order approach that we just talked about it's going to be it a lot so let's quickly summarize all of the important takeaways first one is that we want to use this post-order traversal whenever we have a question

[24:39] that requires us to calculate something at each node based on values that we need from our left and right subtrees and in the code for post odal traversal Solutions we're going to first make those recursive calls then after getting

[24:53] values to calculate something for our current node then finally after that we're going to return some value to our parent and this just allows us to work from the bottom of the tree upwards and solve everything in one traversal which

[25:07] results in the optimal Big O of and time complexity and longest path questions are a specific type of question that can be solved using the post-order traversal for these types of questions you want to think about having each subtree return

[25:21] the longest path that can be extended by its parent the parent's going to have to work out some logic to see how it uses those values to calculate the length of the longest path that runs through its node and then Returns the longest path

[25:33] that can be extended to its parent okay so definitely work through the practice order to really solidify your understanding of how to use that approach and I've also left a couple of more questions that use this post order

[25:46] traversal in the description we just didn't have time to cover it in today's video okay so that's going to be it I hope this helps you all good luck in your interviews don't forget to like comment and subscribe and don't don't

[25:58] forget to head over to hello interview.com if you want more of these types of breakdowns to the most important coding interview patterns all important coding interview patterns all right bye everyone