Terms II

We can describe the sizes of trees and position of nodes using different terminology, like level, depth, and height.

• Level - The level of a node characterizes the distance between the node and the root. The root of the tree is considered level 1. As you move away from the tree, the level increases by one.
  • For our family tree example, what nodes are in the following levels? Think about the answer and then click corresponding arrow.
    Level 1:

    Myra - Level 1 is always the root
    Level 2:

    Raju, Joe, Zia - These are the nodes which are 1 edge away from the root.
    Level 3:

    Uzzi, Bert, Uma - These are the nodes which are 2 edges away from the root.
    Level 4:

    Bev, Ava, Ang - These are the nodes which are 3 edges away from the root.
    Level 5:

    Isla - This is the only node which is 4 edges away from the root.
    Level 6:

    Eoin - This is the only node which is 5 edges away from the root.
• Depth - The depth of a node is its distance to the root. Thus, the root has depth zero. Level and depth are related in that: level = 1 + depth.
  • For our family tree example, what nodes have the following depths?
    Depth 0:

    Myra - The root will always be at depth 0.
    Depth 1:

    Raju, Joe, Zia - These are the nodes which are 1 edge away from the root.
    Depth 2:

    Uzzi, Bert, Uma - These are the nodes which are 2 edge away from the root.
    Depth 3:

    Bev, Ava, Ang - These are the nodes which are 3 edge away from the root.
    Depth 4:

    Isla - This is the only node which is 4 edges away from the root.
    Depth 5:

    Eoin - This is the only node which is 5 edges away from the root.
• Height of a Node - The height of a node is the longest path to a leaf descendant. The height of a leaf is zero.
  • For our family tree example, what nodes have the following heights?
    Height 0:

    Raju, Eoin, Ava, Bert, Ang - The leaves always have height 0.
    Height 1:

    Isla, Uma - `Isla -> Eoin` and `Uma -> Ang`
    Height 2:

    Bev, Zia - `Bev -> Isla -> Eoin` and `Zia -> Uma -> Ang`
    Height 3:

    Uzzi - `Uzzi -> Bev -> Isla -> Eoin`
    Height 4:

    Joe - `Joe -> Uzzi -> Bev -> Isla -> Eoin`
    Height 5:

    Myra - `Myra -> Joe -> Uzzi -> Bev -> Isla -> Eoin`
• Height of a Tree - The height of a tree is equal to the height of the root.
  • Our family tree would have height 5