Trees - Chapter 5

Question 1

In a list, each node has up to one successor. In a blank, each node has up to two children, known as a left child and a right child.

Answer 1

binary tree

Question 2

Blank: A tree node with no children.

Answer 2

Leaf

Question 3

Blank: A node with at least one child.

Answer 3

Internal node

Question 4

Blank A node with a child is said to be that child’s blank.

Answer 4

Parent:

Question 5

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

Answer 5

ancestors

Question 6

Blank: The one tree node with no parent (the “top” node).

Answer 6

Root

Question 7

The link from a node to a child is called an blank.

Answer 7

edge

Question 8

A node’s blank is the number of edges on the path from the root to the node

Answer 8

depth

Question 9

The root node thus has depth blank.

Answer 9

0

Question 10

All nodes with the same depth form a tree blank

Answer 10

level

Question 11

A tree’s blank is the largest depth of any node.

Answer 11

height

Question 12

A tree with just one node has height blank

Answer 12

0

Question 13

A binary tree is blank if every node contains 0 or 2 children.

Answer 13

full

Question 14

A binary tree is blank if all levels, except possibly the last level, contain all possible nodes and all nodes in the last level are as far left as possible.

Answer 14

complete

Question 15

A binary tree is blank, if all internal nodes have 2 children and all leaf nodes are at the same level.

Answer 15

perfect

Question 16

Trees are commonly used to represent blank

Answer 16

hierarchical data

Question 17

A blank can represent files and directories in a file system, since a file system is a hierarchy.

Answer 17

tree

Question 18

Blank is a technique of repeatedly separating a region of space into 2 parts and cataloging objects contained within the regions.

Answer 18

Binary space partitioning (BSP)

Question 19

A blank is a binary tree used to store information for binary space partitioning.

Answer 19

BSP tree

Question 20

Each node in a BSP tree contains information about a blank and which objects are contained in the region.

Answer 20

region of space

Question 21

In graphics applications, a BSP tree can be used to store all objects in a blank. The BSP tree can then be used to efficiently determine which objects must be rendered on screen.

Answer 21

multidimensional world

Question 22

Most of the tree data structures discussed in this book serve to store a collection of values. Numerous tree types exist to store blank in a structured way that allows for fast searching, inserting, and removing of values.

Answer 22

data collections

Question 23

An especially useful form of binary tree is a blank, which has an ordering property that any node’s left subtree keys ≤ the node’s key, and the right subtree’s keys ≥ the node’s key

Answer 23

binary search tree (BST)

Question 24

To search nodes means to find a node with a desired key, if such a node exists. A BST may yield faster searches than a blank Searching a BST starts by visiting the root node (which is the first currentNode below):

Answer 24

list.

Question 25

Searching a BST in the worst case requires H + 1 comparisons, meaning blank comparisons, where H is the tree height.

Answer 25

O(H)

Question 26

A major BST benefit is that an N-node binary tree’s height may be as small as blank, yielding extremely fast searches.

Answer 26

O(logN)

Question 27

A binary tree’s height can be minimized by keeping all levels full, except possibly the last level. Such an “all-but-last-level-full” binary tree’s height is blank

Answer 27

H = floor(log2 N)

Question 28

BST defines an ordering among nodes, from smallest to largest. A BST node’s blank is the node that comes after in the BST ordering, so in A B C, A’s successor is B, and B’s successor is C.

Answer 28

successor

Question 29

A BST node’s blank is the node that comes before in the BST ordering.

Answer 29

predecessor

Question 30

If a node has a right subtree, the node’s successor is that right subtree’s blank:

Answer 30

leftmost child

Question 31

Starting from the right subtree’s root, follow left children until reaching a node with no left child (may be that subtree’s root itself). If a node doesn’t have a right subtree, the node’s successor is the first blank having this node in a left subtree.

Answer 31

ancestor

Question 32

A simple BST blank checks the current node (initially the tree’s root), returning that node as a match, else assigning the current node with the left (if key is less) or right (if key is greater) child and repeating. If such a child is null, the algorithm returns null (matching node not found).

Answer 32

search algorithm

Question 33

Given a new node, a BST blank operation inserts the new node in a proper location obeying the BST ordering property.

Answer 33

insert

Question 34

Blank: If the new node’s key is less than the current node, and the current node’s left child is null, the algorithm assigns that node’s left child with the new node.

Answer 34

Insert as left child

Question 35

Blank: If the new node’s key is greater than or equal to the current node, and the current node’s right child is null, the algorithm assigns the node’s right child with the new node.

Answer 35

Insert as right child

Question 36

Blank: If the left (or right) child is not null, the algorithm assigns the current node with that child and continues searching for a proper insert location.

Answer 36

Search for insert location

Question 37

The BST insert algorithm traverses the tree from the root to a leaf node to find the insertion location. One node is visited per level. A BST with N nodes has at least blank levels and at most blank levels.

Answer 37

log2N
N

Question 38

For a BST, the runtime complexity of insertion is best case blank
and worst case blank

Answer 38

O(logN)
O(N)

Question 39

The space complexity of insertion for a BST is blank because only a single pointer is used to traverse the tree to find the insertion location.

Answer 39

O(1)

Question 40

Given a key, a BST blank operation removes the first-found matching node, restructuring the tree to preserve the BST ordering property.

Answer 40

remove

Question 41

Blank: If X has a parent (so X is not the root), the parent’s left or right child (whichever points to X) is assigned with null. Else, if X was the root, the root pointer is assigned with null, and the BST is now empty.

Answer 41

Remove a leaf node

Question 42

Blank: If X has a parent (so X is not the root), the parent’s left or right child (whichever points to X) is assigned with X’s single child. Else, if X was the root, the root pointer is assigned with X’s single child.

Answer 42

Remove an internal node with single child

Question 43

Blank: This case is the hardest. First, the algorithm locates X’s successor (the leftmost child of X’s right subtree), and copies the successor to X. Then, the algorithm recursively removes the successor from the right subtree.

Answer 43

Remove an internal node with two children

Question 44

STRemove(tree, key) {
parent = null
currentNode = tree⇢root
while (currentNode != null) {
// Check if currentNode has an equal key
if (currentNode⇢key == key) {
if (currentNode⇢left is null && currentNode⇢right is null) {
// Remove leaf

        if (parent is null) { // Node is root
           tree⇢root = null
        }
        else if (parent⇢left == currentNode) {
           parent⇢left = null
        }
        else {
           parent⇢right = null
        }
        return true // Node found and removed
     }
     else if (currentNode⇢right is null) {
        // Remove node with only left child
        
        if (parent is null) { // Node is root
           tree⇢root = currentNode⇢left
        }
        else if (parent⇢left == currentNode) {
           parent⇢left = currentNode⇢left
        }
        else {
           parent⇢right = currentNode⇢left
        }
        return true // Node found and removed
     }
     else if (currentNode⇢left is null) {
        // Remove node with only right child
        
        if (parent is null) { // Node is root
           tree⇢root = currentNode⇢right
        }
        else if (parent⇢left == currentNode) {
           parent⇢left = currentNode⇢right
        }
        else {
           parent⇢right = currentNode⇢right
        }
        return true // Node found and removed
     }
     else {
        // Remove node with two children
        
        // Find successor (leftmost child of right subtree)
        successor = currentNode⇢right
        while (successor⇢left is not null) {
           successor = successor⇢left
        }

        // Copy successor's key to current node
        currentNode⇢key = successor⇢key
        Parent = currentNode

        // Reassign currentNode and key so that loop continues with new key
        currentNode = currentNode⇢right
        key = successor⇢key
     }
     return // Node found and removed
  }
  else if (currentNode⇢key < key) {
     // Search right
     parent = currentNode
     currentNode = currentNode⇢right
  }
  else {
     // Search left
     parent = currentNode
     currentNode = currentNode⇢left
  }    }    return false // Node not found }

Answer 44

BST remove algorithm.

Question 45

The blank traverses the tree from the root to find the node to remove. When the node being removed has two children, the node’s successor is found and a recursive call is made. One node is visited per level, and in the worst case scenario the tree is traversed twice from the root to a leaf.

Answer 45

BST remove algorithm

Question 46

A BST with N nodes has at least log2N
levels and at most N levels. So removal’s worst case time complexity is blank for a BST with log2N
levels and worst case blank
for a tree with N levels.

Answer 46

O(logN)
O(N)

Question 47

In BST removal, two pointers are used to traverse the tree during removal. When the node being removed has two children, a third pointer and a copy of one node’s data are also used, and one recursive call is made. So removal’s space complexity is always
blank.

Answer 47

O(1)

Question 48

A blank algorithm visits all nodes in the tree once and performs an operation on each node.

Answer 48

tree traversal

Question 49

An blank visits all nodes in a BST from smallest to largest, which is useful for example to print the tree’s nodes in sorted order. Starting from the root, the algorithm recursively prints the left subtree, the current node, and the right subtree.

Answer 49

inorder traversal

Question 50

The minimum N-node binary tree height is blank
, achieved when each level is full except possibly the last. The maximum N-node binary tree height is N - 1 (the - 1 is because the root is at height 0).

Answer 50

h = floor(log2 N)

Question 51

Given a node representing a BST subtree, the height can be computed as follows:

If the node is null, return blank.
Otherwise recursively compute the left and right child subtree heights, and return blank.

Answer 51

-1
1 plus the greater of the 2 child subtrees’ heights

Question 52

A BST implementation often includes a blank inside each node. A balanced BST, such as an AVL tree or red-black tree, may utilize the parent pointer to traverse up the tree from a particular node to find a node’s parent, grandparent, or siblings. The BST insertion and removal algorithms below insert or remove nodes in a BST with nodes containing parent pointers.

Answer 52

parent pointer

Question 53

BST search can be implemented using blank. A single node and search key are passed as arguments to the recursive search function. Two base cases exist. The first base case is when the node is null, in which case null is returned. If the node is non-null, then the search key is compared to the node’s key. The second base case is when the search key equals the node’s key, in which case the node is returned. If the search key is less than the node’s key, a recursive call is made on the node’s left child. If the search key is greater than the node’s key, a recursive call is made on the node’s right child.

Answer 53

recursion

Question 54

A recursive BST get-parent algorithm searches for a parent in a way similar to the normal BST search algorithm. But instead of comparing the search key with a candidate node’s key, the search key is compared with the keys of the candidate blank.

Answer 54

node’s children

Question 55

BST insertion and removal can also be implemented using blank. The insertion algorithm uses recursion to traverse down the tree until the insertion location is found. The removal algorithm uses the recursive search functions to find the node and the node’s parent, then removes the node from the tree. If the node to remove is an internal node with 2 children, the node’s successor is recursively remove

Answer 55

recursion

Question 56

A blank is a tree representing a set of strings.

Answer 56

trie (or prefix tree)

Question 57

In a trie, each non-root node represents a single blank. Each node has at most one child per distinct alphabet character.

Answer 57

character

Question 58

A blank is a node that represents a terminating character, which is the end of a string in the trie.

Answer 58

terminal node

Question 59

Tries provide efficient storage and quick search for strings, and are often used to implement blank and blank

Answer 59

auto-complete and predictive text input.

Question 60

Given a string, a trie blank operation creates a path from the root to a terminal node that visits all the string’s characters in sequence.

Answer 60

insert

Question 61

current node pointer initially points to the root. A loop then iterates through the string’s characters. For each character C:

After all characters are processed, a terminal node is added and returned.

Answer 61

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.

Question 62

Given a string, a blank operation returns the terminal node corresponding to that string, or null if the string is not in the trie.

Answer 62

trie search

Question 63

Given a string, a trie blank removes the string’s corresponding terminal node and all non-root ancestors with 0 children.

Answer 63

remove operation

Question 64

Implementations commonly use a lookup table for a trie node’s children, allowing retrieval of a child node from a character in blank time. Therefore, to insert, remove, or search for a string of length M in a trie takes blank time. The trie’s current size does not affect each operation’s time complexity.

Answer 64

O(1)
O(M)

Question 65

A binary search tree can be implemented in Python using blank and blank.

Answer 65

a Node class and a BinarySearchTree class

Question 66

The blank class contains a key value and data members for the left and right children nodes.

Answer 66

Node

Question 67

The blank contains a data member for the tree’s root (a Node object).

Answer 67

BinarySearchTree class

Question 68

The binary search tree search algorithm first assigns current_node with the root. A loop is then entered, and one of three cases occurs:

Answer 68

Case 1: The current node’s key matches the desired key, so current_node is returned from the method.
Case 2: The desired key is less than the current node’s key, so current_node is assigned with current_node.left.
Case 3: The desired key is greater than the current node’s key, so current_node is assigned with current_node.right.

Question 69

The blank is used to insert a new node into the tree. If the tree is empty, then the root data member is assigned with the new node. If the tree is not empty, current_node is assigned with the root node, and a loop is entered. Inside the loop, if the new node’s key is less than the current node’s key, then the new node is inserted as the current node’s left child (if the current node has no left child), or current_node is assigned with current_node.left. If the new node’s key is greater than or equal to the current node’s key, then the new node is inserted as the current node’s right child (if the current node has no right child), or current_node is assigned with current_node.right.

Answer 69

insert() method

Question 70

The remove() method is more complicated than search() and insert() because several cases exist. Different actions are taken depending on what the kind of node is being removed.

Answer 70

Case 1: The node being removed is a leaf. The parent’s left or right data member is assigned with None, depending on which side the node is.
Case 2: The node being removed has one child. The parent’s left or right data member is assigned with the removed node’s single child.
Case 3:The node being removed has two children. The node’s key is replaced by the successor’s key, and then the successor (which will fall under either Case 1 or Case 2) is removed. The successor is the next largest node in the tree, and is always the right child’s leftmost child.