Trees

Question 1

How would you define a tree informally? How can it be implemented in programming?

Answer 1

An abstract data type for hierarchical storage of information.
In programming we can set a pointer at root and then move to an arbitrary element as they are all connected

Question 2

What is a rule about elements, that root and the ends (leafs) of the branches don’t follow?

Answer 2

Each element has a parent and zero or more children

Question 3

Can you think of some examples of trees?

Answer 3

Linux directory structure

Family tree

Question 4

Do you remember the formal definition of a tree?

Answer 4

A tree T is a non-empty set of nodes storing useful information in a parent-child relationship with the following properties:

• T has a special node r referred to as the root
• Each node v of T different from r has a parent node u

Question 5

What do we call external and internal nodes?

Answer 5

External -> leaf node -> 0 children

Internal -> 1 or more children

Question 6

What about the formal definition of a sub-tree (rooted at node v)?

Answer 6

A tree consisting of all the descendants of v in T including v itself

Question 7

How would you describe an ordered tree?

Answer 7

A tree where a linear ordering relation is defined for the children of each node, i.e we can see an order in each level.

Question 8

How would you describe an ordered binary tree? When is it proper?

Answer 8

It is an ordered tree where each node has at most two children. The tree is proper if each internal node has two children (these are labelled left and right child and left comes before right)

Question 9

What is an application of a binary tree?

Answer 9

Arithmetic expression evaluation. Easily apply a traversal algorithm on a binary tree where leaves are numbers and internals are operations.

Question 10

More on programming implementation of trees, how can we access the abstract tree data type?

Answer 10

Using Accesor methods , root(),
parent(v), returns pointer parent node of v
and children(v), returns iterator for children which may
be empty

Question 11

What are more methods that we need on the abstract tree datatype other than the accessors?

Answer 11

Query: isInternal, isExternal, isRoot
Generic: size, elements (i.e iterator of elements at nodes), positions (i.e iterator of all nodes), swapElements(v,w), replaceElement(v,e)

Question 12

What at the complexities of tree ADT methods?

Answer 12

NOT ADDED YET

Question 13

There’s another method we could define to return the depth of a tree T. What is depth of v? What type of algorithm is used to calculate this?

Answer 13

It is the number of ancestors of v, excluding itself.

The depth algorithm is recursive: base case, root depth is 0, step case depth of v is one plus depth of parent.

Question 14

There’s another method we could define to return the height of a tree T. What is height of T? What type of algorithm is used to calculate height of v in T?

Answer 14

height of T = the maximum depth of an external node of T. A recursive algorithm: base case, if v is external height is 0, else it is 1 _ max height of child of a child of v

Question 15

What is tree traversal best described as?

Answer 15

A systematic way of accessing all the nodes of T

Question 16

What are the two different traversal schemes?

Answer 16

Preorder: root visited (and action performed on it )first then subtrees at children visited recursively. action BEFORE calling on subtree
Post order: action after calling on subtree

Question 17

When is preorder traversal useful? What is it’s time complexity?

Answer 17

Produce linear ordering of the nodes in a tree where parents are always before their children.e.g for book example. Time complexity is O(n)

Question 18

When is postorder traversal useful?

Answer 18

Calculating arithmetic expression, finding size of directory

Question 19

What additional accessor methods do binary trees support? What extra annotation can we use on the nodes?

Answer 19

Leftchild(),RightChild(),sibling()

We can now use levels to denote all the nodes of a binary tree at the same depth d as the level d of T

Question 20

If m the number of nodes on level c and n the number of nodes on level d how many times m is n ? (n = X*m)

Answer 20

X = 2

Question 21

What is in-order traversal? What trees can it be performed on?

Answer 21

In order traversal is like a combination of post and pre

Can be performed on binary trees.

Question 22

What data structure could we use to represent a binary tree?

Answer 22

A vector bases structure: Based on simple way of numbering the nodes of T (level numbering function p(v)).

Question 23

What are 2 disadvantages of storing a binary tree in an array, based on a numbering function?

Answer 23

If the tree is not proper there will be blank spaces in the array.

May not have the best performance.

Question 24

What is a more space efficient way to to store a binary tree?

Answer 24

Linked structure. Nodes represented by an object that references element v, and the positions associated with parent and children.

Question 25

How could we use a linked data structure to store general trees (more tan 2 children)?

Answer 25

We would have to add an array between a parent node and it’s children to hole the pointers to the children

Question 26

What abstract data type is the heap data structure based on?

Answer 26

Priority queue

Question 27

what is the heap order property?

Answer 27

Key of child is always greater than or equal to key of parent

Question 28

what are the parts of a heap?

Answer 28

1. the binary tree itself
2. a reference to the (peak) node
3. a comparator

Question 29

What are the two properties we have to maintain when operating on trees?

Answer 29

1. Completeness

2. Heap Order Property

Question 30

What do we call an item in a dictionary?

Answer 30

the (key,element) pair