Trees (chapter 8)

Question 1

Define a tree in terms of models and structure

Answer 1

A tree is an abstract model that stores element hierarchically

Question 2

What does a tree consist of?

Answer 2

consists of nodes that have a parent-child relationship with the exception of the root which is a special node that has no parent. Along with possible subtrees

Question 3

Define internal and external nodes

Answer 3

an internal node is a node that has a child/children. An external node is a node with no children, also known as a leaf

Question 4

Define an edge

Answer 4

an edge is pair of nodes, (u,v) such that u,v have a parent-child relationship.

Question 5

Define a path

Answer 5

a path is a sequence of nodes situated in such a manner that any 2 consecutive nodes in the sequence form an edge

Question 6

In what 3 areas can trees be applied?

Answer 6

1. Organization charts (CEO and employees under him/her)
2. File systems. There is a root folder, I go to documents, then CSC, then lectures but there are many other paths that I can take
3. Programming environments

Question 7

Define a sub-tree

Answer 7

A tree consists of a node and its descendants. A tree can be a subtree of itself

Question 8

Describe the depth of a tree.

Answer 8

• depth is described as the number of edges present from the root of a tree to the particular NODE in question (excluding the node)
• also defined as the number of ancestors a node has (excluding the node)

Question 9

Give code on how to find the depth of a tree recursively

Answer 9

int depth(node v){
if v is root
return 0 
else
return 1 + depth(parent(v))
}

Question 10

What is the height of a tree (hint, an external node has a height of 0)

Answer 10

The height of a tree is the largest depth of a node.

Question 11

Give code to find the height of a node

Answer 11

int height(Node v){
if v isExternal
return 0
else
return 1 + max(height(child(v)))
}

Question 12

What ADT do we use to define a tree why is it useful

Answer 12

We use position ADT, why? Beats me

Question 13

How is a single node in a tree represented?

Answer 13

They are represented by an object that stores an element, a parent of the node, and a sequence of children of the node

Question 14

3 types of tree traversals?

Answer 14

Post order, pre-order and inorder traversal

Question 15

What is a pre-order traversal and where can it be applied?

Answer 15

in a pre-order, a node is visited before its descendants.

the application would be printing a structured document, the headings and subheadings must be printed before the text can be printed.

Question 16

Provide code for pre-order traversal

Answer 16

visit(v)
for each child of v, w
preOrder(w)

• Pre-order is called on each child of the node

Question 17

What happens in a post-order traversal and what are the applications?

Answer 17

the descendants of a node are visited before the node itself

the application would be a computation of the size of files and their subdirectories. You have to first calculate the size of the deepest files and tally them up as you go, only at the end do you get the total size of the folder

Question 18

code for post-order traversals?

Answer 18

for each child w, of v
postOrder(w)
visit(v)

all descendants visited before the node in question is visited

Question 19

What is a binary tree and what are its properties(concerning children)

Answer 19

• A binary tree is a data structure with a parent node having at most 2 children nodes (0,1,2)
• The children of binary trees form an order per and can be distinguished as the left and right child

Question 20

What is a proper binary tree?

Answer 20

It is a binary tree that has the restriction that an internal node must strictly have either 0 or 2 children

Question 21

Define a binary tree in terms of recursion

Answer 21

A tree consisting of a single node, or the root has an ordered pair of children, each of which are a binary tree (being itself or having 2 children, thus a binary tree)

Question 22

What are the applications of a binary tree?

Answer 22

1. Decision-making. A yes or no tree
2. Searching (?)
3. Arithmetic expressions

Question 23

What are the internal and external nodes of an arithmetic binary tree? Decision making?

Answer 23

• internal nodes are operands and external nodes are

* questions are the internal nodes(having yes/no answer), external nodes are the yes/no

Question 24

How does a linked binary tree operate?

Answer 24

An object will store a reference to the element, the parent, the left child and the right child

Question 25

Define a binary tree recursively

Answer 25

A tree with a single node, the root. Or whose root consists of children who form an ordered pair. Each of which form a tree

Question 26

How is an inorder tree implemented and what are its applications?

Answer 26

Left subtree is visited before the parent, the right subtree is visited thereafter.

Application is drawing a binary tree

Question 27

Provide psuedo-code for the inorder traversal

Answer 27

inOrder(Node v){

if(hasLeft(v)){
inOrder(v.left)
}
visit(v)
if(hasRight){
inOrder(v.right)
}
}

Question 28

What is the Euler tour? How many times is each node visited?

Answer 28

Euler tour is a kind of traversal that includes special cases of the pre, in and post traverals. Each node is visited 3 times

Question 29

What is a template method pattern? (3)

Answer 29

• generic algorithm that can be specialized by redefining certain steps
• implemented using an abstract java class
• visit methods are redefined by the subclasses