Chapter 27 - Binary Search Trees

Question 1

In a binary tree, how is the length of a path measured?

Answer 1

The length of a path is the number of the edges (lines between nodes) in the path.

Question 2

How is the depth of a node in a binary tree defined?

Answer 2

The depth of a node is the length of the path from the root to the node.

Question 3

What is a leaf in the binary tree?

Answer 3

A node without children is called a leaf.

Question 4

What is the height of a binary tree?

Answer 4

The height of an empty tree is 0. The height of a nonempty tree is the length of the path from the root node to its furthest leaf + 1. Therefore, height of a tree is either 0 or larger than 1.

Question 5

What is the special property of a binary search tree?

Answer 5

A binary search tree (BST) has the property that for every node in the tree, the value of any node in its left subtree is less than the value of the node, and the value of any node in its right subtree is greater than the value of the node.

Question 6

How can a binary tree be presented/implemented?

Answer 6

A binary heap can be represented using a single array. But a binary tree can also be represented using a set of nodes. Each node contains a value and two links named “left” and “right” that reference the left child and right child, respectively.

Question 7

How can you define a node class for a binary tree?

Answer 7

class TreeNode[E extends Comparable[E» {

• protected E element;
• protected TreeNode[E> left;
• protected TreeNode[E> right;
• public TreeNode(E e) {
• element = e;
• }
  }

Question 8

What is the algorithm for searching for an element in a BST?

Answer 8

You start from the root and scan down from it until a match is found or you arrive at an empty subtree:
Let “current” point to the root. Repeat following steps until current is null or the element matches current.element:
– If element is less than current.element, assign current.left to current
– Else if element is greater than current.element, assign current.right to current
– Else if element is equal to current.element, return true
– Else, current is null, the subtree is empty and the element is not in the tree

Question 9

What is the algorithm for inserting an element into a BST?

Answer 9

If the tree is empty, create a root node with the new element. Otherwise, locate the parent node for the new element node. Create a new node for the element and link this node to its parent node. If the new element is less than the parent element, the node for the new element will be the left child of the parent. If the new element is greater than the parent element, the node for the new element will be the right child of the parent.
If the element is equal to a node, the element is not inserted into the list, because the BST does not keep duplicate elements.

Question 10

What is meant by “tree traversal”?

Answer 10

Three traversal is the process of visiting each node in the tree exactly once.

Question 11

Describe inorder traversal of a BST

Answer 11

With inorder traversal, the left subtree of the current node is visited first recursively, then the current node, and finally the right subtree of the current node recursively. The inorder traversal displays all the nodes in a BST in increasing order.

Question 12

Describe postorder traversal of a BST

Answer 12

With postorder traversal, the left subtree of the current node is visited recursively first, then recursively the right subtree of the current node, and finally the current node itself. An application of postorder is to find the size of the directory in a file system.

Question 13

Describe preorder traversal of a BST

Answer 13

With preorder traversal, the current node is visited first, then recursively the left subtree of the current node, and finally the right subtree of the current node recursively. An application of preorder is to print a structured document.

Question 14

Describe depth-first traversal of a BST

Answer 14

Depth-first traversal is the same as preorder traversal. With preorder traversal, the current node is visited first, then recursively the left subtree of the current node, and finally the right subtree of the current node recursively. An application of preorder is to print a structured document.

Question 15

Describe breadth-first traversal of a BST

Answer 15

With breadth-first traversal, the nodes are visited level by level. First the root is visited, then all the children of the root from left to right, then the grandchildren of the root from left to right, and so on.

Question 16

If a set of elements is inserted into a BST in two different orders, will the two corresponding BSTs look the same? Will the inorder traversal be the same? Will the postorder traversal be the same? Will the preorder traversal be the same?

Answer 16

They will not look the same. The inorder traversal will be the same. The postorder and preorder traversal will not be the same.

Question 17

What is the time complexity of inserting an element into a BST?

Answer 17

O(n)

Question 18

To delete an element from a binary search tree, you need to first locate the node that contains the element and also its parent node. Let “current” point to the node that contains the element to be deleted in the binary search tree and “parent” point to the parent of the “current” node. How do you delete “current” if “current” has no left child?

Answer 18

The current node may be a left child or a right child of the parent node. There are two cases to consider. Case 1 is when current node does not have a left child:
In this case. simply connect the parent with the right child of the current node,
If the current node is a leaf, the parent is connected with null.

Question 19

To delete an element from a binary search tree, you need to first locate the node that contains the element and also its parent node. Let “current” point to the node that contains the element to be deleted in the binary search tree and “parent” point to the parent of the “current” node.
How do you delete “current” if “current” has no right child?

Answer 19

The current node may be a left child or a right child of the parent node. There are two cases to consider. Case 2 is when the current node has a left child:
Let rightMost point to the node that contains the largest element in the left subtree of the current node and parentOfRightMost point to the parent node of the rightMost node. Note that the rightMost node cannot have a right child but may have a left child. Replace the element value in the current node with the one in the rightMost node, connect the parentOfRightMost node with the left child of the rightMost node, and delete the rightMost node.
NOTE: If the left child of “current” does not have a right child, current.left points to the large element in the left subtree of current. In this case, rightMost is current.left and parentOfRightMost is current. You have to take care of this special case to reconnect the right child of rightMost with parentOfRightMost.

Question 20

What is an iterator?

Answer 20

An iterator is an object that provides a uniform way for traversing the elements in a container such as a list, set, binary tree etc.

Question 21

What is the benefit of being a subtype of Iterable[E>?

Answer 21

Being a subtype of Iterable, the elements of the container can be traversed using a for-each loop.

Question 22

What is Huffman Coding?

Answer 22

Huffman coding compresses data by using fewer bits to encode characters that occur more frequently in a text. The codes for the characters are constructed based on the occurrence of the characters in the text using a binary tree, called the Huffman coding tree.

Question 23

How do you build a Huffman coding tree?

Answer 23

To construct a Huffman coding tree, use an algorithm as follows:

1. Begin with a forest of trees. Each tree contains a node for a character. The weight of the node is the frequency of the character in the text.
2. Repeat the following action to combine trees until there is only one tree: Choose two trees with the smallest weight and create a new node as their parent. The weight of the new tree is the sum of the weight of the subtrees.
3. For each interior node, assign its left edge a value 0 and right edge a value 1. All leaf nodes represent characters in the text.

Question 24

What is a greedy algorithm?

Answer 24

A greedy algorithm is often used in solving optimization problems. The algorithm makes the choice that is optimal locally in the hope that this choice will lead to a globally optimal solution.

Question 25

A ____ (with no duplicate elements) has the property that for every node in the tree the value of any node in its left subtree is less than the value of the node and the value of any node in its right subtree is greater than the value of the node.

A. binary tree
B. binary search tree
C. list
D. linked list

Answer 25

B. binary search tree

Question 26

The __ of a path is the number of the edges in the path.

A. length
B. depth
C. height
D. degree

Answer 26

A. length

Question 27

The ___ of a node is the length of the path from the root to the node.

A. length
B. depth
C. height
D. degree

Answer 27

B. depth

Question 28

The ___ of a nonempty tree is the length of the path from the root node to its furthest leaf + 1.

A. length
B. depth
C. height
D. degree

Answer 28

C. height

Question 29

The ___ is to visit the left subtree of the current node first, then the current node itself, and finally the right subtree of the current node.

A. inorder traversal
B. preorder traversal
C. postorder traversal
D. breadth-first traversal

Answer 29

A. inorder traversal

Question 30

The __ is to visit the current node first, then the left subtree of the current node, and finally the right subtree of the current node.

A. inorder traversal
B. preorder traversal
C. postorder traversal
D. breadth-first traversal

Answer 30

B. preorder traversal

Question 31

The __ is to visit the left subtree of the current node first, then the right subtree of the current node, and finally the current node itself.

A. inorder traversal
B. preorder traversal
C. postorder traversal
D. breadth-first traversal

Answer 31

C. postorder traversal

Question 32

In the implementation of BST, which of the following are true?

A. Node is defined as an inner class inside BST.
B. Node is defined as a static inner class inside BST because it does not reference any instance data fields in BST.
C. Node has a property named left that links to the left subtree and a property named right that links to the right subtree and a property named right
D. BST contains a property named root. If tree is empty, root is null.

Answer 32

All are true

Question 33

The time complexity for searching an element in a binary search tree is ___.

A. O(n)
B. O(logn)
C. O(nlogn)
D. O(n^2)

Answer 33

Worst time is O(n), average time is O(logn)

Question 34

A Huffman tree is constructed using the ___ algorithm.

A. dynamic programming
B. divide-and-conquer
C. greedy
D. back-tracking

Answer 34

C. greedy

Question 35

Analyze the following code:

LinkedList[TreeNode[E]] nodeList = new java.util.LinkedList();

for (TreeNode[E> node: nodeList)
{
-   nodeList.add(node.left);
-   nodeList.add(node.right);
-   nodeList.remove(node);
}

Answer 35

You can’t modify a Collection while iterating over it, except for Iterator.remove(). You can also add using ListIterator.add(E e), but this will only insert the item after the current item – you can’t choose where to insert it, e.g. the end of the list.

Your best option is to create another list and add stuff to that as you iterate, e.g. alternating between two lists like in the breadthFirstTraversal method in the BST class.

Question 36

What is a full binary tree?

Answer 36

A full binary tree (sometimes proper binary tree or 2-tree) is a tree in which every node other than the leaves has two children.
Note that this does NOT mean that all the leaves are at the same level.
If the binary tree is a full binary tree, and all the leaves are at the same level, it is called a perfect binary tree.

Question 37

What is a perfect binary tree?

Answer 37

A perfect binary tree is a full binary tree where all the leaves are at the same level.
(A full binary tree is a tree in which every node other than the leaves has two children),
The number of nodes in a perfect binary tree is equal to 2^(number of levels) - 1. E.g., a perfect binary tree with 4 levels has 2^4 - 1 = 15 nodes