Edge
Edge – Connection between one node to another.
Path
Path –
a sequence of nodes and edges connecting a node with a descendant.
A path starts from a
node and ends at another node or a leaf.
Height
Height of node – The height of a node is the
number of edges on the longest downward path between that node and a leaf.
When looking at height:
- Every node has height. So B can have height, so does A, C and D.
- Leaf cannot have height as there will be no path starting from a leaf.
- It 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.
- The height of the root is 1.
Height of tree –The height of a
tree is the number of edges on the longest downward path between the root and a
leaf.
Depth
Depth
–The depth of a node is the number of edges from the node to the tree's root
node.
We don't care about path any more when
depth pops in. We just count how many edges between the targeting node and the
root, ignoring directions. For example, D's depth is 2.
Recall that when talking about height, we actually imply a
baseline located at bottom. For depth, the baseline is at top which is root
level. That's why we call it depth.
Note that the depth of the root is 0.
Level
Level –
The level of a node is defined by 1 + the number of connections between the
node and the root.
Simply, level is
depth plus 1.
The important thing to
remember is when talking about level, it starts from 1 and the level of the root is 1. We need to be careful about this when
solving problems related to level.
