1. Introduction
A tree’s height and depth are important attributes to consider in complexity analysis as well as for numerous algorithms. In this tutorial, we’ll try to show the difference between these two attributes.
2. Problem Explanation
For each node in a tree, we can define two features: height and depth. A node’s height is the number of edges to its most distant leaf node. On the other hand, a node’s depth is the number of edges back up to the root. So, the root always has a depth of 
while leaf nodes always have a height of . And if we look at the tree as a whole, its depth and height are both the root height.
3. Flowchart
Calculating the height or depth for any node can be done using breadth-first search (BFS). But, we’re going to leave the general case for a future post. Simply put, we can find the height recursively by setting the height of the node as the maximum height of its children 
:
For depth, if we assume that each node in the tree stores its parent node, we can traverse from our target node up to the root, counting the edges along the way:
4. Pseudocode
Let’s see these two now side-by-side. As stated earlier, with height, we traverse downwards and depth, upwards:
|
|
|
5. Complexity
We can also compare their complexities. Since we used BFS for finding the height, the complexity is 
where n is the number of nodes in the tree. As for the depth algorithm, we iterate over the edges from the target node up to the root. Thus, we can easily see that the time complexity for finding the depth of a node is 
, and the worst case will be . Also, the space complexity is for finding height and depth. In the case of finding the height, we need to allocate memory for the BFS queue (which is allocated automatically in the recursive solution). And we need to allocate space for the parents in the case of finding the depth.
6. Conclusion
In this short article, we showed the difference between tree height and depth. To do this, we examined approaches for calculating them and compared their space-time complexities.