Trees

Question 1

What type of data structure is a tree?

Answer 1

A hierarchical data structure

Question 2

What internal data structure is used in a heap?

Answer 2

A queue

Question 3

What is a node?

Answer 3

The elements of a data structure

Question 4

What is an edge?

Answer 4

The theoretical relationship between a parent and child node

Question 5

What are the two special cases of nodes?

Answer 5

root: topmost node
leaf: bottommost node

Question 6

What is the length a measure of?

Answer 6

The number of nodes in a path

Question 7

What is the height of a tree?

Answer 7

The largest depth(length of path)

Question 8

What is the depth?

Answer 8

The length from the root node to the destination

Question 9

What are some common uses for trees?

Answer 9

1. )represent family trees, like genealogy
2. )represent decision making algorithms
3. )represent priority queues(as a heap)
4. )provide fast access to databases(as a b-tree)

Question 10

What is a sub-tree?

Answer 10

The tree with a root node that is a descendant of the original root node.

Question 11

What are the descendants of a node?

Answer 11

The subsequent children of a given parent node

Question 12

What kind of relationship does a tree have that differs from the predecessor/successor of a list?

Answer 12

parent/child relationship

Question 13

What are the requirements for a tree to be considered binary?

Answer 13

Each parent node has 2 children, a right and left node

Question 14

What defines pre-order traversal?

Answer 14

Root-L-R

Question 15

What defines post-order traversal?

Answer 15

L-R-Root

Question 16

What defines level-order traversal?

Answer 16

Root-level1-level2-leveln…

Question 17

What defines in-order traversal?

Answer 17

L-Root-R

Question 18

What is BST short for?

Answer 18

Binary Search tree

Question 19

When is a binary tree a BST?

Answer 19

If for every node, the right subtree(k) is greater than the node(k) & the left subtree(k) is smaller

Question 20

Are duplicates allowed in a standard BST?

Answer 20

no. The insert makes sure of this by throwing a DuplicateException

Question 21

For the recursive lookup method of a BST, what base cases are there?

Answer 21

1. ) the tree is empty

2. ) the root node has the value we are searching for

Question 22

For the recursive lookup method of a BST, what recursive cases are there?

Answer 22

1. ) visit the right subtree

2. ) visit the left subtree

Question 23

How is the insert method implemented for a BST?

Answer 23

It is the same as the lookup method, but after finding the desired position it is added as a child of the parent

Question 24

What three cases have to be considered when deleting a node in a BST?

Answer 24

The node to delete has:

• 1 node
• 2 nodes
• no nodes(is a leaf)

Question 25

What does the complexity of the lookup method depend on in a BST?

Answer 25

The combination of inserts/delete that shape the graph

Question 26

What BST will yield a faster lookup?

Answer 26

A bulkier tree that is more balanced O(log N), whereas more linear trees will yield a complexity closer to O(N)

Question 27

What are some examples of balanced trees?

Answer 27

AVL, 2-4, b-trees & red-black trees

Question 28

What fields does a treeNode have?

Answer 28

data, child node pointers. These are set to null when there's less than the maximum amount

Question 29

When deleting a node from a BST, what is the n node replaced with for all three cases?

Answer 29

0: set parent to null 1: set parent to n 2: set n to numerically adjacent node (right subtree far left)

Question 30

What represents a priority queue?

Answer 30

A heap

Question 31

What type is a heap?

Answer 31

a class of binary tree with the ORDER and SHAPE property

Question 32

What is the order property?

Answer 32

All children nodes are smaller than their parent nodes

Question 33

What is the shape property?

Answer 33

All leaves are at the last or second to last level | All leaves at the bottom level are as far left as possible

Question 34

What is implied if the shape property is true?

Answer 34

The tree is complete

Question 35

What is a full tree?

Answer 35

where the d-1 level all have two children and all interior nodes are not null

Question 36

For an array implementation of a heap, where is the root node?

Answer 36

array[1]

Question 37

If a node is on array[k], where is the left node 1 & right node?

Answer 37

array[2k] & array[2k + 1], respectively

Question 38

Where does the insert operation add a node to a heap?

Answer 38

@ the end of the array i.e. the bottom level to the right.. Then swap parents until the order property is satisfied

Question 39

What is the largest value in a heap?

Answer 39

The root

Question 40

How does the removeMax operation work?

Answer 40

replaces root with the array[last], then swaps with the largest child until order property is satisfied

Question 41

What complexity are the methods of a heap?

Answer 41

O(log N)

Question 42

Is a heap balanced?

Answer 42

yes

Question 43

When is a tree height balanced?

Answer 43

When the right and left trees are balanced and their leaves are at levels that differ no more than 1