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

User · Answer

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  amp  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 lt  i lt 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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

[algorithm] What is the difference between tree depth and height?

Examples related to algorithm

Examples related to data-structures

Examples related to tree

Examples related to nodes

Examples related to terminology