What's the difference between node height and depth in a Binary tree?

Other Questions Notion
1

I’m trying to understand Binary trees better. But I’m really confused about how to define the height and depth of a node. Different sources seem to say different things.

Here’s what I think it means:

  • Height: The longest path from a node to a leaf
  • Depth: How many steps it takes to get from a node to the root

I made a little tree to help explain:

    A
   / \
  B   C
 / \
D   E
   / \
  F   G

So for node E:

  • Level: 3
  • Height: 1
  • Depth: 2

But I’m not sure if this is right. Also, I don’t get why a single node (just the root) has a height of 1. Can someone help me understand this better?

2

Your understanding of depth is spot on. For height, you’re close, but there’s a slight difference. Height is typically measured as the number of edges in the longest path from a node to a leaf, not the number of nodes. So in your example, E’s height would indeed be 1, not 2. As for a single node tree, its height is usually defined as 0, not 1. This convention helps maintain consistency in algorithms and makes certain calculations more straightforward. Remember, these definitions can vary slightly depending on the context or specific implementation, but the edge-counting method for height is generally more common in computer science literature and algorithms.

3

I’ve worked extensively with binary trees in my projects, and I can share some insights. The confusion around height and depth is common, but here’s how I’ve come to understand it:

Height is about the longest downward path, while depth is about the upward path to the root. For height, we count edges, not nodes. So a leaf node has height 0, not 1. This took me a while to grasp, but it makes sense when you think about it.

In your example, E’s height is indeed 1 (one edge to F or G), and its depth is 2 (two edges up to A). The single root node having height 0 threw me off at first too, but it’s a convention that simplifies many algorithms.

Remember, these definitions can vary slightly in different contexts, but this approach has served me well in practice. It’s crucial to be consistent within your own implementations.

4

i think ur almost there, but height is count by edges not nodes. e.g. node e has height 1 not 2 cause it’s one edge to a leaf, and a solo root gets height 0. hope that helps get it!