---
title: 'Coding Interview Fundamentals: Post-Order Traversal'
source: 'https://youtube.com/watch?v=suPO02S0cR8'
video_id: 'suPO02S0cR8'
date: 2026-08-04
duration_sec: 1567
---

# Coding Interview Fundamentals: Post-Order Traversal

> Source: [Coding Interview Fundamentals: Post-Order Traversal](https://youtube.com/watch?v=suPO02S0cR8)

## Summary

This video teaches the post-order traversal technique for solving binary tree problems in coding interviews. It starts with the classic 'diameter of a binary tree' problem to illustrate the motivation, then applies the technique to three additional questions, including a hard problem frequently asked by top tech companies.

### Key Points

- **Introduction to Post-Order Traversal** [00:02] — The video focuses on post-order traversal as the most important technique for solving binary tree questions using recursion. It will cover a classic interview question and three additional applications.
- **Diameter of a Binary Tree** [00:43] — The first problem is finding the diameter of a binary tree, defined as the longest path between any two nodes (number of edges). The diameter does not have to pass through the root.
- **Top-Down Approach (Brute Force)** [02:02] — The top-down approach calculates the longest path through each node by computing heights of left and right subtrees. This leads to O(n^2) runtime due to repeated work.
- **Bottom-Up Approach (Optimal)** [04:18] — The bottom-up approach starts from the leaf nodes, calculates the longest path through each node using subtree heights, and returns heights to parents. This visits each node once, resulting in O(n) time.
- **Code for Optimal Solution** [06:42] — The optimal solution uses a single recursive function that returns the height of the subtree and updates a global variable 'max' with the longest path found. The calculation is done after recursive calls, which is post-order traversal.
- **When to Use Post-Order Traversal** [11:06] — Use post-order traversal when you need to calculate something at each node based on values from its left and right subtrees. This allows working from the bottom up in one traversal.
- **Tilt of a Binary Tree** [12:01] — The second problem is finding the tilt of a binary tree, defined as the sum of absolute differences between left and right subtree sums at each node. This also uses post-order traversal.
- **Longest Univalue Path** [15:01] — The third problem is finding the longest path where all nodes have the same value. The key is that each node returns the longest univalue path that can be extended by its parent.
- **Binary Tree Maximum Path Sum** [21:46] — The final problem is finding the maximum path sum in a binary tree, rated as hard. It uses the same bottom-up approach, returning the maximum path that can be extended by the parent.
- **Summary and Key Takeaways** [24:26] — Post-order traversal is used when calculations depend on subtree values. Longest path problems require each subtree to return the longest path extendable by its parent. This yields O(n) time complexity.

### Conclusion

Post-order traversal is a fundamental technique for solving binary tree problems efficiently, especially those involving longest paths or calculations based on subtree values. Mastering this approach allows you to solve a variety of interview questions with optimal O(n) time complexity.

## Transcript

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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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+
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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