5 BINARY SEARCH TREES

Question 1

What is a binary search tree?

Answer 1

A dynamic data structure that supports efficient addition, removal, and searching of elements.

Question 2

What are the key advantages of binary search trees over sorted arrays?

Answer 2

Efficient addition and removal of elements in addition to searches.

Question 3

What is the structure of a binary search tree?

Answer 3

A hierarchical data structure composed of nodes, where each node has a value and up to two pointers to child nodes.

Question 4

What are internal nodes and leaf nodes in a binary search tree?

Answer 4

Internal nodes have at least one child, while leaf nodes do not have any children.

Question 5

What minimal information does a binary search tree node contain?

Answer 5

A value (or key), pointers to two child nodes, and an optional pointer to the parent node.

Question 6

How is the binary search tree property defined?

Answer 6

For any node N, the value of any node in N’s left subtree is less than N’s value, and the value of any node in N’s right subtree is greater than N’s value.

Question 7

What is the implication of the binary search tree property on node values?

Answer 7

It restricts the binary search tree to contain unique values.

Question 8

True or False: Binary search trees can be defined to allow duplicate values.

Answer 8

True.

Question 9

What is the role of pointers in a binary search tree?

Answer 9

Pointers link nodes to their children and parents, allowing traversal through the tree structure.

Question 10

How do we search for a value in a binary search tree?

Answer 10

By walking down from the root node and comparing the current node’s value with the target value.

Question 11

What happens if the target value is less than the current node’s value during a search?

Answer 11

The search progresses to the left subtree.

Question 12

What happens if the target value is greater than the current node’s value during a search?

Answer 12

The search progresses to the right subtree.

Question 13

What are the two approaches to implement a search in a binary search tree?

Answer 13

Iterative and recursive approaches.

Question 14

What does the recursive search function return if the target value is not found?

Answer 14

Null.

Question 15

In the context of a binary search tree, what does a dead end indicate?

Answer 15

A node that does not match the target value and does not have a child in the correct direction.

Question 16

Describe the iterative search function for a binary search tree.

Answer 16

It uses a WHILE loop to traverse down the tree, checking values and reassigning the current node until the target is found or a dead end is reached.

Question 17

What is the computational cost of searching in a binary search tree?

Answer 17

Proportional to the depth of the target value in the tree.

Question 18

How does the structure of a binary search tree affect search efficiency?

Answer 18

Minimizing the tree’s depth increases search efficiency.

Question 19

What is the primary concern when comparing binary search trees to sorted arrays?

Answer 19

Whether the added complexity and overhead of pointers are worth it compared to a single binary search on a sorted array.

Question 20

Fill in the blank: A binary search tree starts at a single _______ node.

Answer 20

root

Question 21

What is the purpose of auxiliary data in a binary search tree node?

Answer 21

To store additional information related to the node’s value, enhancing the data structure’s utility.

Question 22

Why might a sorted array be preferable over a tree for a single search?

Answer 22

Building a tree is more expensive than a single linear scan.

Question 23

What is a key advantage of using binary search trees in dynamic data environments?

Answer 23

Binary search trees allow efficient addition and removal of data points.

Question 24

What is the first step when searching for a node in a binary search tree?

Answer 24

Start at the root node.

Question 25

What happens when inserting the first node into a binary search tree?

Answer 25

That node becomes the new root.

Question 26

What does the wrapper data structure for a binary search tree simplify?

Answer 26

Handling of the root node and provides an easy-to-use interface.

Question 27

What is the purpose of checking if the tree is empty at the start of a search?

Answer 27

To immediately return null if the search fails.

Question 28

How do we add a value to a binary search tree?

Answer 28

Start at the root, progress down the tree, and create a new node at a dead end.

Question 29

What do we do if we encounter a duplicate value when inserting into a binary search tree?

Answer 29

Update the node as needed or keep going to insert a new copy.

Question 30

What is the cost of inserting a new node into a binary search tree proportional to?

Answer 30

The depth of the branch along which we insert the new node.

Question 31

What are the three cases of node removal in a binary search tree?

Answer 31

* Removing a leaf node * Removing an internal node with a single child * Removing an internal node with two children

Question 32

What happens when we remove a leaf node from a binary search tree?

Answer 32

We delete the node and update its parent's child pointer.

Question 33

How do we remove an internal node with a single child?

Answer 33

Promote the single child to be the child of the deleted node's parent.

Question 34

What is the process for removing an internal node with two children?

Answer 34

Swap it with its successor in the tree.

Question 35

How do we find the successor of a node in a binary search tree?

Answer 35

It is the minimum node in the right-hand subtree.

Question 36

What is a critical advantage when finding a node's successor?

Answer 36

The successor will have at most one right-hand child.

Question 37

What does the pseudocode in Listing 5-1 illustrate?

Answer 37

The removal of three types of nodes from a binary search tree.

Question 38

What must we check before removing a node from a binary search tree?

Answer 38

Whether the tree is empty and if the node is valid (not null).

Question 39

In the case of removing a leaf node, what does the code check first?

Answer 39

If the node to be deleted has a parent node.

Question 40

True or False: When removing a node with two children, we can simply delete the node.

Answer 40

False.

Question 41

Fill in the blank: To remove a node with two children, we swap it with its _______.

Answer 41

successor.

Question 42

What is the result of removing a leaf node in terms of the parent node's structure?

Answer 42

The parent node may become a leaf.

Question 43

What programming structure can simplify the management of a binary search tree's root node?

Answer 43

A thin wrapper data structure.

Question 44

What function is used to remove a node from a binary search tree?

Answer 44

RemoveTreeNode(tree, FindTreeNode(tree, target))

Question 45

What does FindTreeNode return if the node is not found?

Answer 45

null

Question 46

In case A of node removal, what happens when removing a leaf node?

Answer 46

Change the correct child pointer of the removed node’s parent to null

Question 47

What should be checked first when removing a leaf node?

Answer 47

Whether the node to be deleted has a parent node

Question 48

What modification is made if the removed node is the root?

Answer 48

Modify the root node pointer to null

Question 49

In case B, what is the first step when removing a node with a single child?

Answer 49

Identify which of the node’s two child pointers links to the child

Question 50

What does the code do after identifying the child node in case B?

Answer 50

Fixes the pointers between the newly promoted node and its new parent

Question 51

How does the code handle the case of a node with two children?

Answer 51

Identifies the successor node and removes that from the tree

Question 52

What is the worst-case runtime of deletion in a binary search tree?

Answer 52

Proportional to the depth of the tree

Question 53

What is a perfectly balanced binary search tree?

Answer 53

A tree where the right subtree contains the same number of nodes as the left subtree

Question 54

What is the worst-case performance of operations in a balanced tree?

Answer 54

Proportional to log2(N)

Question 55

What happens to a binary search tree when it becomes highly unbalanced?

Answer 55

Its depth could grow linearly with the number of elements

Question 56

What is a potential result of inserting values in sorted order into a binary search tree?

Answer 56

Creation of a sorted linked list

Question 57

What can be the time complexity of operations on an unbalanced tree with N nodes?

Answer 57

Time linearly proportional to N

Question 58

Name three types of trees that can help keep binary search trees balanced.

Answer 58

* Red-black trees * 2-3 trees * B-trees

Question 59

What is the bulk construction method for creating balanced binary search trees?

Answer 59

Recursively dividing elements into smaller subsets

Question 60

How do we select the node value during bulk construction from a sorted array?

Answer 60

Choose the middle value to be the node at that level

Question 61

What do we use to track the current range of the array during bulk construction?

Answer 61

Indices of the highest and lowest values

Question 62

What happens when only a single value is left in the range during construction?

Answer 62

Create a new leaf node with that value and no children

Question 63

Why are binary search trees important in data structures?

Answer 63

They maintain ordering information and facilitate efficient searches

Question 64

What concept will be introduced in the next chapter that extends binary search tree concepts?

Answer 64

The trie