Introduction

In the last module, we covered the underlying vocabulary of trees and how we can implement our own tree. To recall, we covered: node, edge, root, leaf, parent, child, and degree.

For this module we will expand on trees and gain a better understanding of how powerful trees can be. As before, we will use the same tree throughout the module for a guiding visual example.

Terms I

Many of the terms used in trees relate to terms used in family trees. Having this in mind can help us to better understand some of the terminology involved with abstract trees. Here we have a sample family tree.

• Ancestor - The ancestors of a node are those reached from child to parent relationships. We can think of this as our parents and our parent’s parents, and so on.
  • Let’s look at all of the ancestors of each of our nodes in the family tree.
    • Ava’s ancestors: Uzzi, Joe, Myra. This is because, Uzzi is the parent of Ava, Joe is the parent of Uzzi, and Myra is the parent of Joe. Try to work out the following and click the name to reveal the ancestors.
    Uma:

    Zia, Myra - **Zia** is the parent of Uma and **Myra** is the parent of Zia.
    Myra:

    None - Myra does not have a parent node.
    Raju:

    Myra - **Myra** is the parent of Raju.
    Bev:

    Uzzi, Joe, Myra - **Uzzi** is the parent of Bev, **Joe** is the parent of Uzzi, and **Myra** is the parent of Joe.
• Descendant - The descendants of a node are those reached from parent to child relationships. We can think of this as our children and our children’s children and so on.
  • Let’s look at all of the descendants of each of our nodes in the family tree.
    • Ava’s descendants: None. Ava has no child nodes and thus, no descendants. Try to work out the following and click the name to reveal the descendants.
    Uma:

    Ang - **Ang** is the child of Uma
    Myra:

    Raju, Joe, Zia, Uzzi, Bert, Uma, Bev, Ava, Ang, Isla, Eoin - All of the nodes in a tree will be descendants of the root. To work it out: **Raju, Joe** and **Zia** are the children of Myra, **Uma** is the child of Zia, **Ang** is the child of Uma, and we can work the rest out for Joe's children.
    Raju:

    None - Raju has no child nodes.
    Bev:

    Isla, Eoin - **Isla** is the child of Bev and **Eoin** is the child of Isla.
• Siblings - Nodes which share the same parent
  • We can think about the siblings of all of our nodes in the family tree.
    • Ava’s siblings: Bev - Uzzi is the parent node of Ava; Uzzi has two child nodes, Ava and Bev. Try to work out the following and click the name to reveal the siblings.
    Uma:

    None - Zia is the parent node of Uma; Zia has only one child node, Uma.
    Myra:

    None - Myra is the root and thus does not have a parent node resulting in no siblings.
    Raju:

    Joe, Zia - Myra is the parent node of Raju; Myra has three child nodes, **Joe**, **Zia**, and Raju
    Bev:

    Ava - Uzzi is the parent node of Bev; Uzzi has two child nodes, Bev and **Ava**.

Recursion Refresh

In principle, the recursive case breaks the problem down into smaller portions until we reach the base case. Recursion presents itself in many ways when dealing with trees.

Trees are defined recursively with the base case being a single node. Then we recursively build the tree up. With this basis for our trees, we can define many properties using recursion rather effectively.

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

Terms III

When working with multidimensional data structures, we also need to consider how they would be stored in a linear manner. Remember, pieces of data in computers are linear sequences of binary digits. As a result, we need a standard way of storing trees as a linear structure.

• Path - a path is a sequence of nodes and edges, which connect a node with its descendant. We can look at some paths in the tree above:

  • From Q to O: QRO
  From `Q` to `Y`:

  `QWY`
  From `R` to `P`:

  `RP`

• Traversal is a general term we use to describe going through a tree. The following traversals are defined recursively.

Preorder Traversal

1. Access the root, record its value.
2. Run the preorder traversal each of the children

• The Pre refers to the root, meaning the root goes before the children.
• Remember: Root Children
• For the above tree, the preorder traversal could result in: QWYUERIOPTA

Postorder Traversal

1. Run the postorder traversal on each of the children
2. Access the root, record its value

• The Post refers to the root, meaning the root goes after the children.
• Remember: Children Root
• For the above tree, the postorder traversal could result in: YUWEIOPRATQ

When we talk about traversals for general trees we have used the phrase ’the traversal could result in’. We would like to expand on why ‘could’ is used here. Each of these general trees are the same but their traversals could be different. The key concept in this is that for a general tree, the children are an unordered set of nodes; they do not have a defined or fixed order. The relationships that are fixed are the parent/child relationships.

MyTree Recursive I

Again, we want to be able to implement a working version of a tree. From the last module, we had functions to add children, remove children, get attributes, and instantiate MyTree. We will now build upon that implementation to create a true tree.

MyTree with recursion

Recall that in the previous module, we were not yet able to enforce the no cycle rule. We will now enforce this and add other tree functionality.

In the first module, we discussed how we can define trees recursively, meaning a tree consists of trees. We looked at the following example. Each red dashed line represented a distinct tree, thus we had five trees within the largest tree making six trees in total.

We will use our existing implementation from the first module. Now to make our tree recursive, we will include more getter functions as well as functions for traversals and defining node relationships.

Get depth, height, size, and root

We can define each of these recursively.

Get Depth

• Depth - The depth of a node is its distance to the root. Thus, the root has depth zero.

We can define the depth of a node recursively:

• Base case: we are at the root and the depth is zero
• Recursive case: for any other node, the depth is 1 plus the depth of the parent

function GETDEPTH()
    if ROOT
        return 0
    else 
        return 1 + PARENT.GETDEPTH()
end function

Get Height

• Height of a Node - The height of a node is the longest path to a leaf descendant. The height of a leaf is zero.

We can define the height of a node recursively:

• Base case: we are at the leaf and the height is zero
• Recursive case: for any other node, return 1 plus the maximum height of its children

function GETHEIGHT()
    if LEAF
        return 0
    else 
        MAX = 0
        for CHILD in CHILDREN
            CURR_HEIGHT = CHILD.GETHEIGHT()
            if CURR_HEIGHT > MAX
                MAX = CURR_HEIGHT
        return 1 + MAX
end function

Get Root

• Root - the topmost node of the tree; a node with no parent.

We can define returning the root recursively:

• Base case: we are at the root so return it
• Recursive case: for any other node, return the root of the nodes parent

function GETROOT()
    if ISROOT()
        return this tree
    else
        return PARENT.GETROOT()
end function

Get Size

We define the size of a tree as the total number of children.

function GETSIZE()
    SIZE = 1
    for CHILD in CHILDREN
        SIZE += CHILD.GETSIZE()
    return SIZE
end function

Find a Value

To find a value within our tree, we will traverse down a branch as far as we can until we find the value. This will return the tree that has the value as the root.

function FIND(VALUE)
	if ITEM is VALUE
		return this node
	for CHILD in CHILDREN
		FOUND = CHILD.FIND(VALUE)
		if FOUND is not NONE
			return FOUND
	return NONE
end function

MyTree Recursive II

Determine relationships (Ancestor, Descendant, Sibling)

We can determine many relationships within the tree. For example, given a node is it an ancestor of another node, a descendant, or a sibling?

Is Ancestor?

For this function, we are asking: is this node an ancestor of the current instance? In this implementation, we will start at our instance and work down through the tree trying to find the node in question. With that in mind, we can define this process recursively:

• Base case: we are at the node in question, so return true OR we are at a leaf so return false.
• Recursive case: run the method from each of the children of the node.

function ISANCESTOR(TREE)
    if at TREE
        return true
    else if at LEAF
        return false
    else 
        for CHILD in CHILDREN
            FOUND = CHILD.ISANCESTOR(TREE)
            if FOUND
                return true
        return false
end function

Is Descendant?

For this function, we are asking: is this node a descendant of the current instance? In this implementation, we will start at our instance and work up through the tree trying to find the node in question. With that in mind, we can define this process recursively:

• Base case: we are at the node in question, so return true OR we are at the root so return false.
• Recursive case: run the method from the parent of the node.

function ISDESCENDANT(TREE)
    if at TREE
        return true
    else if at ROOT
        return false
    else 
        return PARENT.ISDESCENDANT(TREE)
end function

Is Sibling?

For this function, we are asking: is this node a sibling of the current instance? To determine this, we can get the parent of the current instance and then get the parents children. Finally, we check if the node in question is in that set of children.

function ISSIBLING(TREE)
    if TREE in PARENT's CHILDREN
        return true
    else 
        return false
end function

Lowest common ancestor

In any tree, we can say that the root is a common ancestor to all of the nodes. We would like to get more information about the common ancestry of two nodes. For this function, we are asking: which node is the first place where this instance and the input node’s ancestries meet? Similar to our ISDESCENDANT, we will work our way up the tree to find the point where they meet

• Base case: we are at our tree so return the tree OR we are at an ancestor of our tree so return the instance OR we are at the root so return nothing
• Recursive case: run the method from the parent.

function LOWESTANCESTOR(TREE)
    if at TREE
        return TREE
    else if ISANCESTOR(TREE)
        return instance
    else if at ROOT
        return NONE
    else
        return PARENT.LOWESTANCESTOR(TREE)
end function

Path from the root

This function will generate the path which goes from the root to the current instance.

function PATHFROMROOT(PATH)
    if NOT ROOT
        PARENT.PATHFROMROOT(PATH)
    append ITEM to PATH
end function

MyTree Recursive III

Traversals

In this module we have talked about two traversals: preorder and postorder. Both of these are defined recursively and the prefix refers to the order of the root.

Preorder

In a preorder traversal, first we access the root and then run the preorder traversal on the children.

function PREORDER(RESULT)
    append ITEM to RESULT
    FOR CHILD in CHILDREN
           CHILD.PREORDER(RESULT)
end function

Postorder

In a postorder traversal, first we run the postorder traversal on the children then we access the root.

function POSTORDER(RESULT)
   FOR CHILD in CHILDREN
           CHILD.POSTORDER(RESULT)
   append ITEM to RESULT
end function

Summary

In this section, we discussed more terminology related to trees as well as tree traversals. To recap the new vocabulary:

• Ancestor - The ancestors of a node are those reached from child to parent relationships. We can think of this as our parents and the parents of our parents, and so on.
• 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.
• Descendant - The descendants of a node are those reached from parent to child relationships. We can think of this as our children and our children’s children and so on.
• Height of a Node - The height of a node is the longest path to a leaf descendant. The height of a leaf is zero.
• Height of a Tree - The height of a tree is equal to the height of the root.
• Level - The level of a node characterizes the distance the node is from the root. The root of the tree is considered level 1. As you move away from the tree, the level increases by one.
• Path - a sequence of nodes and edges which connect a node with its descendant.
• Siblings - Nodes which share the same parent
• Traversal is a general term we use to describe going through a tree. The following traversals are defined recursively.
  • Preorder Traversal (Remember: Root Children):
    1. Access the root
    2. Run the preorder traversal on the children
  • Postorder Traversal (Remember: Children Root):
    1. Run the postorder traversal on the children
    2. Access the root.