Chapter 27 - Binary Search Trees Flashcards
In a binary tree, how is the length of a path measured?
The length of a path is the number of the edges (lines between nodes) in the path.
How is the depth of a node in a binary tree defined?
The depth of a node is the length of the path from the root to the node.
What is a leaf in the binary tree?
A node without children is called a leaf.
What is the height of a binary tree?
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.
What is the special property of a binary search tree?
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.
How can a binary tree be presented/implemented?
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.
How can you define a node class for a binary tree?
class TreeNode[E extends Comparable[E» {
- protected E element;
- protected TreeNode[E> left;
- protected TreeNode[E> right;
- public TreeNode(E e) {
- element = e;
- }
}
What is the algorithm for searching for an element in a BST?
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
What is the algorithm for inserting an element into a BST?
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.
What is meant by “tree traversal”?
Three traversal is the process of visiting each node in the tree exactly once.
Describe inorder traversal of a BST
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.
Describe postorder traversal of a BST
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.
Describe preorder traversal of a BST
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.
Describe depth-first traversal of a BST
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.
Describe breadth-first traversal of a BST
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.
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?
They will not look the same. The inorder traversal will be the same. The postorder and preorder traversal will not be the same.
What is the time complexity of inserting an element into a BST?
O(n)
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?
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.
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?
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.
What is an iterator?
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.
What is the benefit of being a subtype of Iterable[E>?
Being a subtype of Iterable, the elements of the container can be traversed using a for-each loop.
What is Huffman Coding?
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.
How do you build a Huffman coding tree?
To construct a Huffman coding tree, use an algorithm as follows:
- 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.
- 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.
- 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.
What is a greedy algorithm?
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.
