Week 5

Question 1

Tree

Answer 1

A set of interconnected nodes with no closed circuits or loops

Question 2

Subtree

Answer 2

A tree rooted an internal node of the tree

Question 3

Leaf(terminal node)

Answer 3

Any tree rooted an internal node of the tree

Question 4

Root node

Answer 4

The first node of the tree

Question 5

Branch

Answer 5

A link between two nodes within the tree

Question 6

Degree of a node

Answer 6

Number of subtrees of that node

Question 7

Level of a node

Answer 7

Number of branches on the path from the root to the node

Question 8

Height / Depth of a tree

Answer 8

Number of nodes on the longest path from the root node to a leaf node

Question 9

What is a Binary tree ?

Answer 9

Is a special case of a tree where every node is of degree two or less

Question 10

A Binary Search Tree is a special case of a Binary tree where :

Answer 10

*The keys in the left subtree of the root precede the key in the root
*The key in the root node precedes the keys
*The left and right subtrees of the root are also Binary Search Trees

Question 11

The first item is based on the normal binary search algorithm where:

Answer 11

*The first item to be tested will be stored in the root node
*If the required item is stored in this node then our search is complete
*If the required item comes before the data item stored in the root node then we will search the left subtree
*If the required item comes after the data item stored in the root node then we will search the right subtree
*The search will then process until either we locate the required data item or we reach a leaf node when we know that the required item is not stored in the BST

Question 12

Cases to be considered before deleting a node from a BST

Answer 12

*The node is a leaf node
*The node has one subtree
*The node has two subtrees

Question 13

Types of approaches to the traversal of a binary tree:

Answer 13

*Depth First Traversal (DFT)
*Breadth First Traversal (BFT)

Question 14

Depth First Traversal (DFT)

Answer 14

The traversal proceeds along a path from the root through one child to the MOST distant descendant of that first child before processing the second child. To
implement this traversal a STACK is used.

Question 15

Breadth First Traversal (BFT)

Answer 15

The traversal proceeds HORIZONTALLY from the root to all of its children then to its
children’s children and so on until all nodes have been processed. To implement this
traversal a QUEUE is used.

Question 16

Things that needed to do before each node in Depth First Traversal (DFT) operates :

Answer 16

*Visit the node
*Traverse the Left subtree
*Traverse the Right subtree