18

I am doing a refresher an algorithms and data structures.

I am confused on the concept of depth vs height of a tree. In many cases, especially on sites focusing on interview quizes, it seems to me that these terms are used interchangeably.

It seems to me that the basic literature defines them as applicable to a node and not to a tree.

So the depth of the root (which is a node) is 0. The height of root (or any subnode) is the max height of its children.

But when you apply these terms on a tree i.e. find the max depth of a tree, it seems that these terms now are "meaningless" and can be used interchangeably i.e. to find the max depth just calculate max height.

For example in this post Check if tree is balanced the answers focus on the height of the tree while the definition of balance could be on the depth of the tree

Is my understanding correct or am I messing up on these fundamentals?

Community
  • 1
  • 1
Cratylus
  • 52,998
  • 69
  • 209
  • 339
  • People define either term in different ways. Most notably, you can count edges or nodes, yielding different notions (though only off by one). So I would not fuss about that. Make sure to check the definition in every case and stick to it. – Raphael Dec 11 '11 at 15:59

9 Answers9

9

When talking about a tree they mean the same thing: the length of the longest path from the root to a leaf node.

Tudor
  • 61,523
  • 12
  • 102
  • 142
  • But a tree defined recursively can be only a root (empty subtrees for children). In this case the depth of the root is `0` and the depth of the tree is `1` altough the tree is nothing else but the root? – Cratylus Dec 11 '11 at 18:17
  • The depth is also 0 because there are no edges if there is only the root. – Tudor Dec 11 '11 at 18:23
7

The depth is usually used to describe a property of a tree node, while the height is used to describe the property of the entire tree, as in the following examples:

  • Root node has a depth of zero
  • Node X has a depth of N
  • The height of the tree is M

The height of a tree is defined as the depth of its deepest node.

Sergey Kalinichenko
  • 714,442
  • 84
  • 1,110
  • 1,523
  • 1
    In literature the height is also defined as a property of a node. Formally the height of a node is the length of the longest path of the node to the leaf – Cratylus Dec 11 '11 at 16:30
4

The height of a node is the length of the longest downward path to a leaf from that node. The height of the root is the height of the tree.

The depth of a node is the length of the path to its root (i.e., its root path). This is commonly needed in the manipulation of the various self-balancing trees, AVL Trees in particular. The root node has depth zero, leaf nodes have height zero, and a tree with only a single node (hence both a root and leaf) has depth and height zero. Conventionally, an empty tree (tree with no nodes, if such are allowed) has depth and height −1.

gsdf
  • 275
  • 1
  • 6
  • 13
4

a depth is "how deep a node is" [or how far is it from the root]. height is "how high the tree is" [or, how far is the the farest leaf from it]

Formally:

height(v) = 0                                                              v is a leaf
            max{height(u)|for every u such that u is a son of v} + 1       else

depth(v) = 0                                                                v root
           depth(u) + 1    where u is the parent of v                       else

EDIT: when referring to the max depth concept, it is identical to the height of a tree [which is maximal at the root], you can prove it by induction.

amit
  • 175,853
  • 27
  • 231
  • 333
  • He asked whether they mean the same thing about a tree. – Tudor Dec 11 '11 at 15:08
  • When you calculate the maxHeight and the maxDepth of the tree, don't you get the same number? – Cratylus Dec 11 '11 at 15:10
  • @amit:But a tree defined recursively can be only a root (empty subtrees for children). In this case the depth of the root is `0` and the depth of the tree is `1` altough the tree is nothing else but the root? – Cratylus Dec 11 '11 at 18:17
0
private static int getHeight(BTreeNode n){

    if(n == null)
        return 0;

    int lHeight = getHeight(n.left);
    int rheight = getHeight(n.right);

    int height = 1+Math.max(lHeight,rheight);

    return height;
}
kleopatra
  • 51,061
  • 28
  • 99
  • 211
user3209952
  • 1
0

Depth of a Node: is a length of a path from the root to a node. Height of a Node: is a length of a path from the node to the innermost node(leaf).

But height and depth in case of tree are the same. Height of tree = Depth of a tree = Maximum height = Maximum depth.

avishek gurung
  • 188
  • 2
  • 7
0

In Binary search tree

  1. Height of a node: # edges on the longest simple downward path from the node to a leaf
  2. Height of a tree: height of the root
  3. Depth of a node: length of simple path (# edges) from root to the node
Hasitha
  • 558
  • 1
  • 12
  • 26
0

Height Of the Node is with reference to Leaf - length of longest path to the leaf node from the source node.

Depth of the Node is with reference to root Node. - total length from source node to root

But when you are talk in general about whole tree both refers to same, it differs only if you take a particular node within the tree

nandy
  • 101
  • 1
  • 4
0

Height of a tree is number of nodes from root to leaf following the longest path. So if we have one node (root itself) height=1 Empty tree: 0

And depth or level of any node is number of edges from root node to that node. so..depth of root is 0.

In this way max depth of tree is one less than height of tree.

SunilDwivedi
  • 1