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?
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.
https://i.stack.imgur.com/8yPi9.png
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.....
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.
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.
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.
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.
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
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.
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.
https://i.stack.imgur.com/aBbeM.jpg
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
The “depth” (or equivalently the “level number”) of a node is the number of edges on the “path” from the root node
The “height” of a node is the number of edges on the longest path from the node to a leaf node.
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```
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.
Success story sharing