Week 7 of the course¶

Self-study¶

The topics for this week are (i) Graphs and Trees, (ii) Tree data structures and traversals and (iii) Invalidation in containers

The following links will take you to the video-lectures and the accompanying slides:

Graphs and Trees¶

Graphs and Trees: part 1.

Graphs and Trees: part 2.

Graphs and Trees: part 3.

slides for Graphs and Trees

Tree data structures and traversals¶

Tree data structures and traversals part 1.

Tree data structures and traversals: part 2.

slides for Tree data structures and traversals

Invalidation in containers¶

Invalidation in containers

slides for Invalidation

Trees¶

Question 1

With regard to a general rooted tree, which of the following are true? (Note: more than 1 statement may be true.)

A node can have at most 2 parents.

A node with no children is called a leaf.

A node with no parent is called a root.

If a node has more than 1 child, then none of the children can be leaves.

A node, whose parent has no other children, is called a lonesome node.

Question 2

Suppose we are considering the subtrees of node \(x\) in some rooted tree. Which of the following is true?

Each of the subtrees of \(x\) has \(x\) as its root.

The number of subtrees of \(x\) is one more than the number of children of \(x\).

The parent of \(x\) does not belong to any of the subtrees of \(x\).

Each child of \(x\) belongs to exactly two subtrees of \(x\).

Question 3

Suppose we are considering a rooted tree whose height is 4. Which of the following statements is always true?

The root has at least 4 children.

The tree has at most 4 leaves.

Starting from the root, we need to use at least 5 edges to get to the leaf that is farthest from the root.

The tree has at least 5 nodes.

Question 4

Let \(x\) be a node in a rooted tree. A descendant of node \(x\) is any node in any subtree of \(x\). Which of the following statements is always true?

A child of \(x\) has fewer descendants than \(x\).

The number of descendants of the root is the same as the number of nodes in the tree.

Each leaf is a descendant of all non-leaf nodes in the tree.

No two non-leaf nodes can have the same number of descendants.

Tree data structures and traversals¶

Question 1

Assume a node in a binary tree is stored using children pointers left_child and right_child. If the entire binary tree has 4 nodes, how many of these children pointers will be equal to nullptr?

it is impossible to know how many

Question 2

Which of the following best describes the difference between how a node is stored in a general rooted tree and how a node is stored in binary tree?

With regard to a pointer to node’s parent, in a binary tree we never need such a pointer, whereas in a general tree we sometimes need such a pointer.

With regard to pointers to a node’s children, in a binary tree we have two separate pointers, whereas in a general tree we need some container (e.g. a vector) to store these pointers.

With regards to a node’s key or identification number, in a binary tree such a key must be divisible by 2, whereas for a general tree it can be any positive integer.

With regards to the root node, in a binary tree the root must have exactly 2 children, whereas in a general tree the root can even have a negative number of children.

Question 3

Suppose we perform preorder and postorder traversals on an entire rooted tree having at least two nodes. Which of the following is true?

The numbers of nodes visited by the two different traversals are not equal.

The order in which the nodes are visited in the two traversals is different.

The first node visited in each traversal is a leaf.

Neither traversal needs to know what are the children of any node.

Question 4

Three tree traversals were presented, preorder, postorder and inorder. In what way does inorder differed from the other two traversals?

Only trees with no leaves can be traversed with inorder traversal. The other two can be used to traverse any tree.

A binary tree can only be traversed with inorder traversal. A binary tree cannot be traversed using either postorder or preorder.

An inorder traversal can only be done on trees having the following property: each node has exactly two children.

An inorder traversal can only be done on a binary tree. Preorder and postorder traversals can be done any tree.

Invalidation¶

Question 1

With regard to invalidation and different STL containers, which of the following statements is true? (More than 1 statement may be true.)

For all containers, using an invalidated iterator is not a problem because the STL-library always checks for invalidated iterators.

For some containers there are operations that can cause all iterators to be invalidated.

For a given container, there are well defined operations which will cause invalidated iterators.

There are some containers for which iterator invalidation can never occur.

Question 2

What can be said in general about invalidation and iterators, pointers and indices?

Invalidation is only a problem with iterators and pointers. An index of a vector or array cannot become invalidated.

Only iterator invalidation will cause a program to crash. Invalidated pointers or indices will only cause the program to slow down.

Invalidation of an iterator or a pointer or an index can only occur when using STL-functions.

Programs can be written using iterators and pointers and indices in which invalidation does not occur.

Question 3

What does invalidation cause when using an STL container?

The source code for the STL-container becomes corrupted.

Indirect references to some elements (pointers, iterators) become unusable.

All elements of the container are removed.

A user must change the C++ compiler he or she has been using.

Question 1

What is a central question, related to this course, whose answer can be found in this week’s videos?

Question 2

Of the following topics, which do you think deserves further discussion/explanation during the weekly consultation session?

Trees and graphs

Tree data structures

Tree traversals

Invalidation

Question 3

Were there any parts of the video lectures that were particularly difficult? Particularly interesting? Something about which you wish to learn more?

Extra links on the topic:

Week07 - Glossary

Submit weekly exercises¶

Questions to be submitted this week