Confusion between the notion of height and depth of a node in Binary tree

Question

I have been doing some research on Binary trees and found that every other source gives different notion for depth and height of a node in Binary tree.

My notion

Height = Maximum length of path from a given node to the leaf node.

Depth = Number of edges from a given node to the root node.

        /*         
         *         1         (1)    level = 1, height = 3, depth = 0
         *        / \ 
         *       2   3       (3)    level = 2, height = 0, depth = 1
         *      / \    
         *     4   5         (5)    level = 3, height = 1, depth = 2
         *        / \ 
         *       6   7       (6, 7) level = 4, height = 0, depth = 3
         */

I have taken this notion from this blog post, but I am confused when there is just one node i.e. root its height is 1.

@ZaphodBeeblebrox see my last line of the question. That link doesn't explain that doubt. — CodeYogi, Oct 21 '15 at 12:49
http://stackoverflow.com/questions/4065439/height-of-a-tree-with-only-one-node Doing a little search, before asking, does not harm. — Zaphod Beeblebrox, Oct 21 '15 at 13:28
@zaphod what makes you think that I haven't searched anything? Do I came up with my theory of height and depth? I am not asking what they are, I am simply asking that out of various notions I chose this one because it felt more intuitive to me, the only confusion remains with the height of the root node. And seriously you didn't see the link to blog post? Common! — CodeYogi, Oct 21 '15 at 18:16
@CodeYagi "what makes you think that I haven't searched anything?" The fact that the link I posted answers your question? — Zaphod Beeblebrox, Oct 22 '15 at 18:50

davidawad · Answer 1 · 2015-10-21T12:48:43.677

Well, level is just an unintuitive word because of the way we look at something like trees in a visual representation.

According to this blog post, The level of a node is defined by 1 + the number of connections between the node and the root.

In which case all of those levels make sense. 7 is 3 connections away from 1.

However, you also have some incorrect heights. Remember, Height is the longest path from the node to a leaf. So A's height is the number of edges of the path to E, NOT to G. And its height is 3.

  5
 /  \
6    7

in that example, 5 has 1 row of children and those children are leaf nodes, so it's height is 1. But if you considered 6 and 7 as individual trees themselves, their heights are 0, because they are leaf nodes.

score 0 · Answer 2 · answered Oct 21 '15 at 12:46

0

Simply speaking, the depth of a node is the number of edges you have to traverse starting from the root to reach that node. Height of a node is the number of edges you have to traverse downwards starting from that node to reach the farthest node. The height of a tree is the height of its root.

answered Oct 21 '15 at 12:46

turingcomplete

2,128
3
16
25

what is the case when we have just a single node? what will be its height? – CodeYogi Oct 23 '15 at 04:50
@CodeYogi in that case it'll be zero. – turingcomplete Oct 23 '15 at 11:41
so, you say that single node is considered leaf not root, right? – CodeYogi Oct 23 '15 at 11:44
@CodeYogi A single node is considered to be both a leaf and a root. Leaf because it has no children, and root because it has no parents. – turingcomplete Oct 23 '15 at 15:16

score 0 · Answer 3 · answered Oct 21 '15 at 12:46

From the post you linked:

Height of node – The height of a node is the number of edges on the longest downward path between that node and a leaf.

I think it say the height of the root is 1, refering to the example with the single root.

In your example, i think it should be:

/*         
     *         1         (1)    level = 1, height = 3, depth = 0
     *        / \ 
     *       2   3       (3)    level = 2, height = 0, depth = 1
     *      / \    
     *     4   5         (5)    level = 3, height = 1, depth = 2
     *        / \ 
     *       6   7       (6, 7) level = 4, height = 0, depth = 3
     */

edit: Ok you corrected your post, so the relevant point in my post is I think it say the height of the root is 1, refering to the example with the single root.

Confusion between the notion of height and depth of a node in Binary tree

My notion

3 Answers3