What is the difference between tree depth and height?

Question

This is a simple question from algorithms theory.
The difference between them is that in one case you count number of nodes and in other number of edges on the shortest path between root and concrete node.
Which is which?

Solution 1

I learned that depth and height are properties of a node:

• The depth of a node is the number of edges from the node to the tree's root node.
  A root node will have a depth of 0.

• The height of a node is the number of edges on the longest path from the node to a leaf.
  A leaf node will have a height of 0.

Properties of a tree:

• The height of a tree would be the height of its root node,
  or equivalently, the depth of its deepest node.

• The diameter (or width) of a tree is the number of nodes on the longest path between any two leaf nodes. The tree below has a diameter of 6 nodes.

Solution 2

height and depth of a tree is equal...

but height and depth of a node is not equal because...

the height is calculated by traversing from the given node to the deepest possible leaf.

depth is calculated from traversal from root to the given node.....

Solution 3

According to Cormen et al. Introduction to Algorithms (Appendix B.5.3), the depth of a node X in a tree T is defined as the length of the simple path (number of edges) from the root node of T to X. The height of a node Y is the number of edges on the longest downward simple path from Y to a leaf. The height of a tree is defined as the height of its root node.

Note that a simple path is a path without repeat vertices.

The height of a tree is equal to the max depth of a tree. The depth of a node and the height of a node are not necessarily equal. See Figure B.6 of the 3rd Edition of Cormen et al. for an illustration of these concepts.

I have sometimes seen problems asking one to count nodes (vertices) instead of edges, so ask for clarification if you're not sure you should count nodes or edges during an exam or a job interview.

Solution 4

I know it's weird but Leetcode defines depth in terms of number of nodes in the path too. So in such case depth should start from 1 (always count the root) and not 0. In case anybody has the same confusion like me.

Solution 5

Simple Answer:
Depth:
1. Tree: Number of edges/arc from the root node to the leaf node of the tree is called as the Depth of the Tree.
2. Node: Number of edges/arc from the root node to that node is called as the Depth of that node.

View more solutions

Comments

[Péter Török]

+1 was about to add quote with same content from here: en.wikipedia.org/wiki/Tree_%28data_structure%29

[Gabriel Ščerbák]

hmm I thought the terminology is not ambiguous, however thanks for the link.

[VINOTH ENERGETIC]

Is there is any differnce in counting the nodes and edges. Seems to be both will give the same result. Correct me if i am wrong.

[roottraveller]

is that means height == max depth

[Daniel A.A. Pelsmaeker]

@rkm_Hodor: Yes, the height of a tree is always equal to the depth of the deepest node.

[mightyWOZ]

"height is calculated by traversing from leaf to the given node" it is not correct , the leaf must be the one which is deepest among all the leaves of the given node.

[Biranchi]

Very well explained regarding height and depth in Binary trees.

[chitti]

"Note that depth doesn't make sense for a tree" - Why isn't the depth useful?

[neowulf33]

@jdhao how can the depth of root be 2? It's either 0 (if edges are considered) or 1 (if nodes are considered).

[jdhao]

@neowulf33, yes, I am terribly wrong. The depth of the root node should be 0. I will delete my comment in order not to confuse people.

[Ankit Roy]

Could you please cite a source for your claim that diameter of a tree counts nodes instead of edges? This conflicts with the usual definition of the diameter of a graph (see e.g. en.wikipedia.org/wiki/Distance_(graph_theory)) which asks for the longest path.

[Daniel A.A. Pelsmaeker]

@j_random_hacker It's a matter of definition, pick the one most useful to you. To get from the number of vertices to the number of edges, just subtract 1. I prefer to count the number of vertices, as this results in a graph with only one node having width 1, and an empty graph having width 0. mathworld.wolfram.com/GraphDiameter.html

[kaya3]

For what it's worth, the definition at this link has been changed to: "The depth of a node M in the tree is the length of the path from the root of the tree to M. The height of a tree is the depth of the deepest node in the tree."

[Jin Tiger]

I am confused some website says count nodes, here it says count edges. in this link, it talks about finding maximum depth, in the example it gives, the depth of the tree is 3, but if I count edges it will be 2. geeksforgeeks.org/…

[sphoenix]

On a different note, depth == number_of_level of a binary tree.

[ranka47]

Hi Diva. As the question already has an accepted answer and this particular answer do not add any additional details. You may find some related discussion about the SO policy here

[Yash Verma]

Nice way to remember. Thanks!

[Jerry An]

In leetcode.com/problems/maximum-depth-of-binary-tree, the depth of the root is 1 instead of 0, pls explain it for me?

[brian beuning]

Other answers say the same thing in clearer manner.

[Taimur Ahmed Qureshi]

@ashtree: Did you mean to say that the height of this tree is 3, and not 4?

[ashtree]

@TaimurAhmedQureshi Looks like since I posted, they changed the definition, which ^kaya3 noted. So originally the height would have been 4, but with kaya3's answer, now, yes it's 3.

[Otieno Rowland]

Is that so? See leetcode.com/problems/diameter-of-binary-tree which defines it in terms of edges.