Ch 4: Trees

Question 1

what is a binary tree?

Answer 1

a tree where each node has up to two “children”: left and right child

Question 2

what is a leaf?

Answer 2

a tree node with no children

Question 3

what is an internal node?

Answer 3

a node with at least one child

Question 4

what is the parent?

Answer 4

a node with a child is said to be the child’s parent

Question 5

what are ancestors?

Answer 5

the node’s parent, the parent’s parent, etc. up to the tree’s root

Question 6

what is a root node?

Answer 6

the one tree node with no parent (“top” node)

Question 7

what is an edge?

Answer 7

a link from a node to a child

Question 8

what is a node’s depth?

Answer 8

number of edges on the path from the root to the node

Question 9

what is a tree’s height?

Answer 9

the largest depth of any node

Question 10

what is the height of a tree with no nodes?

Answer 10

height is 0

Question 11

when is a tree full?

Answer 11

every node contains 0 or 2 children

Question 12

when is a tree complete?

Answer 12

when all levels, except possibly the last level, contain all possible nodes and all nodes in the last level are as far left as possible

Question 13

when is a tree perfect?

Answer 13

when all internal nodes have 2 children and all leaf nodes are at the same level

Question 14

what are trees commonly used to represent?

Answer 14

hierarchical data

Question 15

what is binary space partitioning (BSP)?

Answer 15

a technique of repeatedly separating a region of space into two parts and cataloging objects contained within the regions

Question 16

what is a BSP tree?

Answer 16

a binary tree used to store information for BSP

Question 17

what is in each node of a BSP tree?

Answer 17

holds information about a region of space and which objects are contained in this region

Question 18

what is a binary search tree (BST)?

Answer 18

• a form of a binary tree that has an ordering property that any node’s left subtree keys are less than the nodes keys and the right subtree keys are more than the nodes keys
• ordering property allows for faster searching

Question 19

what is search?

Answer 19

to find a node with a desired key, if such node exists

Question 20

what is a successor?

Answer 20

the node that comes after in the BST ordering

Question 21

what is a predecessor?

Answer 21

the node that comes before in the BST ordering

Question 22

what is the search algorithm?

Answer 22

given a key, returns first node found watching key or null if matching node with found

Question 23

what is insert?

Answer 23

an operation that inserts a new node in a proper location obeying the BST ordering property

Question 24

what is remove?

Answer 24

an operation that removes the first-found matching node, restructuring the tree to preserve the BST ordering property

Question 25

what is tree traversal?

Answer 25

an algorithm that visits all nodes in the tree once and performs an operation on each node

Question 26

what is in-order traversal?

Answer 26

visits all nodes in a BST from smallest to largest

Question 27

what is in-order traversal useful for?

Answer 27

when printing tree’s nodes in sorted order

Question 28

what is a trie (prefix tree)?

Answer 28

a tree representing a set of strings

Question 29

what does each node represent in a trie?

Answer 29

represents a single character and has at most one child per distinct alphabet character

Question 30

what is a terminal node?

Answer 30

represents a terminating character, which is the end of a string in the trie

Question 31

what is trie insert

Answer 31

an operation that creates a path from the next to a terminal node that visits all the string’s characters in a sequence

Question 32

explain the trie insert algorithm

Answer 32

a current node pointer initially points to root node, then a loop iterates through the string’s characters. for each character C, a new child node is added only if the current node does not have a child for C. the current node pointer is assigned with the current node’s child for C. after all characters are processed, a terminal node is added and returned

Question 33

what is trie search?

Answer 33

an operation that returns the terminal node corresponding to that string, or null if the string is not in the trie

Question 34

what is trie remove?

Answer 34

an operation that removes the string’s corresponding terminal code and non-root ancestors with 0 children

Question 35

explain BST insert algorithm

Answer 35

1. if root is null then node is set to root
2. if root isn’t null, then if key is less than root it’ll check if root’s left is empty. if it is then node is placed. other wise it’ll check again if key is greater than or less than the node and keep traversing until it finds it spot
3. if root isn’t null and key is more than root it’ll check Iif roots right is empty. if it is then node is placed otherwise it’ll check again if key is greater than or less than the node and keep traversing until it finds it spot

Question 36

explain BST remove algorithm

Answer 36

1. search for a matching node in the tree
2. if found:
   - if node is a leaf node, the node is removed and parents left/right is set to null, if node was root then root is set to null and tree is empty
   - if node is an internal node with one child, then the parent node’s child will be set to the current node’s child
   - if node is an internal node with two children, the successor is found (the right most child in node’s subtree) and copied in place of the current node. the originally successor is deleted

Question 37

explain BST inorder traversal algorithm

Answer 37

1. current node points to root
2. if root is null, return otherwise printInOrder is recursively called on root’s left, then current node is printed, then printInOrder is recursively called on root’s right