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?
324
votes
Tip: to avoid confusion between terminologies: 1. Height: Imagine measuring a person's height, we do it from toe to head (leaf to root). 2. Depth: Imagine measuring depth of a sea, we do it from earth's surface to ocean bed (root to leaf).
– Yesh
@Yesh This is a great analogy.
– Special Character
To add on to @Yesh excellent analogy: for some inner node in the middle of the tree, it's depth is how many levels it is beneath the root node, and it's height is how levels it is above its bottom-most child node.
– Thomas Nguyen
be careful here guys - height is measured head to toe, just like it's defined from node to leaf, and would be traversed down in a tree. Just think of a stick figure that lost a leg. The node there doesn't define his height, because it's not the longest path. We can though, say we found the depth of that node
– devdev_dev
10 Answers
790
votes
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.
50
votes
17
votes
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.
7
votes
5
votes
3
votes
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.
3
votes
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 n1, n2,...,nk is a sequence of nodes in the tree such that ni is the parent of ni+1 for 1<=i<k, then this sequence is called a path from n1 to nk. 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.
2
votes
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.
0
votes
-1
votes
The overall depth of the tree is equal to the height of the tree and the same for the level of the tree but if for a particular node height is not equal to the depth because the definition of Depth states that the longest path from the root node to that node, In case of Height it is from that node to the leaf node.
overall tree, D=H=L but for a node D=L But D may not be equal to H.
