algorithmdata-structurestreenodesterminology

What is the difference between depth and height in a tree?


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?


Solution

  • 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.

    A tree, with height and depth of each node