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?

Answer 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.

Answer 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.....

Answer 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.

Answer 4

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.

Answer 5

Another way to understand those concept is as follow: Depth: Draw a horizontal line at the root position and treat this line as ground. So the depth of the root is 0, and all its children are grow downward so each level of nodes has the current depth + 1.

Height: Same horizontal line but this time the ground position is external nodes, which is the leaf of tree and count upward.

Answer 6

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.

Answer 7

I wanted to make this post because I'm an undergrad CS student and more and more we use OpenDSA and other open source textbooks. It seems like from the top rated answer that the way height and depth is being taught has changed from one generation to the next, and I'm posting this so everyone is aware that this discrepancy now exists and hopefully won't cause bugs in any programs! Thanks.

From the OpenDSA Data Structures & Algos book:

If n₁, n₂,...,n_k is a sequence of nodes in the tree such that n_i is the parent of n_i+1 for 1<=i<k, then this sequence is called a path from n₁ to n_k. The length of the path is k−1. If there is a path from node R to node M, then R is an ancestor of M, and M is a descendant of R. Thus, all nodes in the tree are descendants of the root of the tree, while the root is the ancestor of all nodes. 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 one more than the depth of the deepest node in the tree. All nodes of depth d are at level d in the tree. The root is the only node at level 0, and its depth is 0.

Figure 7.2.1: A binary tree. Node A is the root. Nodes B and C are A's children. Nodes B and D together form a subtree. Node B has two children: Its left child is the empty tree and its right child is D. Nodes A, C, and E are ancestors of G. Nodes D, E, and F make up level 2 of the tree; node A is at level 0. The edges from A to C to E to G form a path of length 3. Nodes D, G, H, and I are leaves. Nodes A, B, C, E, and F are internal nodes. The depth of I is 3. The height of this tree is 4.

Answer 8

The answer by Daniel A.A. Pelsmaeker and Yesh analogy is excellent. I would like to add a bit more from hackerrank tutorial. Hope it helps a bit too.

• The depth(or level) of a node is its distance(i.e. no of edges) from tree's root node.
• The height is number of edges between root node and furthest leaf.
• height(node) = 1 + max(height(node.leftSubtree),height(node.rightSubtree)).
  Keep in mind the following points before reading the example ahead.
• Any node has a height of 1.
• Height of empty subtree is -1.
• Height of single element tree or leaf node is 0.
  

Answer 9

1. Depth:

---

The depth of a node in the tree is the length of the path from the root to the node. The depth of the tree is the maximum depth among all the nodes in the tree.

2. Height:

---

The height of the node is the length of the path from that node to the deepest node in the tree. The height of the tree is the length of the path from the root node to the deepest node in the tree. (Eg: the height of the tree in the above example is four (count the edges, not the nodes)). A tree with only one node has zero height.

For more reference about basics of trees, visit: INTRODUCTION AND PROPERTIES OF TREES

Answer 10

Depth: how many edges are there above the node that is depth of a node
Height: how many edges are there below the node that is height of a node

 Node1 // depth = 0 and height = 2 => root node
  |
 / \
Node2 Node3 //depth = 1 and height = 1
|     |
Node4 Node5  //depth = 2 and height = 0  => leaf node```