Mod 5

Question 1

In a tree, what is a parent?

Answer 1

A node P in a tree is called the parent of another node C if P has an edge that points directly to C.

Question 2

In a tree, what is a descendant and what is an ancestor?

Answer 2

The descendants of a node N are all of N’s children, plus its children’s children, plus the children of those nodes, and so forth.

A node A is the ancestor of another node D if D is a descendant of A.

Question 3

Can a tree have two roots?

Answer 3

The ancestor of all other nodes in the tree is called the root. Each tree has exactly one root.

Question 4

How is an interior node different from a leaf node?

Answer 4

A node in a tree is an interior node if it has at least one child.

node in a tree is a leaf node (or just a leaf) if it has no children. When implementing a tree, a leaf node conventionally will not reference any child nodes (e.g., in Python these references would be set to None.)

Question 5

What is a subtree?

Answer 5

A subtree is the portion of a tree that consists of a single node N, all of N’s descendants, and the edges joining these nodes. We call this the subtree rooted at N.

Question 6

In a tree with n nodes, how many subtrees exist?

Answer 6

n-1. We can make a subtree out of each node except the root (as that would be the same tree).

Question 7

What is a path and how do we find the path length?

Answer 7

A path is the collection of edges in a tree joining a node to one of its descendants.

The length of a path in a tree is equal to the number of edges in that path.

Question 8

What is node depth?

Answer 8

The depth of a node N in a tree is the length of the path from the root to N. By definition, the root node has depth 0.

Question 9

What is tree height?

Answer 9

A tree’s height is the maximum depth of any node in the tree.

Question 10

How is a full binary tree different from a perfect binary tree?

Answer 10

A full binary tree is a binary tree in which every node has exactly two child nodes or zero child nodes (i.e. a leaf).

A perfect binary tree is a full binary tree (i.e., one where all interior nodes have two children) where all the leaves are at the same depth. Importantly, if we know a perfect binary tree has height h, then we know:

It has 2h leaves.
It has 2h+1 - 1 total nodes.

Hence, a perfect binary tree is different in that it does not have any leaves at a depth less than the height of the tree.

Question 11

What is a complete binary tree?

Answer 11

a complete binary tree is a binary tree that is perfect except for the deepest level, where all the nodes are all as far left as possible.

Question 12

What is a binary search tree?

Answer 12

A binary search tree (or BST), then, is a binary tree that satisfies the following property (known as the “binary search tree property”):

Within a binary search tree, the key of each node N is greater than all the keys in N’s left subtree and less than or equal to all the keys in N’s right subtree.

Question 13

What is the difference between a depth-first and breadth-first traversal?

Answer 13

• Depth-first – A depth-first traversal explores a tree subtree by subtree, visiting all of a node’s descendants before visiting any of its siblings (and their descendants). To put it another way, depth-first traversal moves as far downward in the tree as it can go before moving across in the tree.
• Breadth-first – A breadth-first traversal explores a tree level by level, visiting every node at a given depth in the tree before moving downward and traversing the nodes at the next-deepest level. In other words, a breadth-first traversal moves as far across the tree as it can go before moving down in the tree.

Question 14

Excluding traversals that go from right to left, name three kinds of depth first traversals?

Answer 14

1. Preorder traversal – NLR – process the current node before traversing either of its subtrees
2. Inorder traversal – LNR – traverse the current node’s left subtree before processing the node itself, and then traverse the node’s right subtree
3. Postorder traversal – LRN – traverse both of the current node’s subtrees (left, then right) before processing the node itself

Question 15

Describe the steps to find an element in a binary search tree.

Answer 15

Given a query key kq, here’s how it works:

1. Examine one node at a time. Keep a pointer to the current node, starting at the root.
2. If the current node is None, the key kq doesn’t exist in the tree, and the search has failed. Return failure.
3. If the current node’s key is equal to kq, the search has succeeded. Return success.
4. Otherwise, if kq is less than the current node’s key, move the current node pointer to point to its left child and repeat.
5. Otherwise, kq is greater than the current node’s key, so we move the current node pointer to point to its right child and repeat.

find(bst, kq):
n ← bst.root
while n is not None:
if n.key equals kq:
return success
else if kq < n.key:
n ← n.left
else:
n ← n.right
return failure

Question 16

What is a node’s inorder predecessor and successor?

Answer 16

The inorder successor for a node with key k is simply the node corresponding to the very next key after k in the tree’s ordered list of keys. Similarly, the same node’s inorder predecessor is the node corresponding to the key before k in the ordered list of keys.

Ex: 2 10 17 30 32 64 72 73 75 77 90

For example, the inorder successor of the root node in our example BST (whose key is 64) is the node with key 72, since 72 comes immediately after 64 in the sorted list of keys.

Now that we know what an inorder successor is, how do we actually find the inorder successor of a given node in a BST? A node n’s inorder successor is always the leftmost node in n’s right subtree.

Question 17

How to insert a new element in a binary search tree?

Answer 17

insert(bst, k, v):
p ← None
n ← bst.root
while n is not None:
p ← n
if k < n.key:
n ← n.left
else:
n ← n.right
create a new node as the child of p containing k, v

Observe that the node is always being inserted as a leaf.

Question 18

How do we remove a node with no child or one child?

Answer 18

If the element to be removed is stored in a leaf node (i.e., a node with no children, like the one with key 2 in the BST depicted above), we can simply free that node and update its parent to have a None child.

If the element to be removed is stored in a node with just a single child, we can simply free that node and move its child to become a child of the node’s parent.

Question 19

How do we remove a node with two children in a binary search tree?

Answer 19

remove(bst, k):
n, pn ← find the node to be removed and its parent
based on key k, as in the find() function
if n has no children:
update pn to point to None instead of n
else if n has only 1 child:
update pn to point to n’s child instead of n
else:
s, ps ← find n’s inorder successor and its
parent, as described above
s.left ← n.left
if s is not n.right:
ps.left ← s.right
s.right ← n.right
update pn to point to s instead of n
free n

Question 20

Describe the runtime complexities of operations in a BST.

Answer 20

Each of the three operations (find, insert, and remove) has a runtime complexity of O(h) (where h is the height of the tree) as each operation relies on a search function that performs a constant time comparison at each level of the tree.

Of course, for a fixed number of nodes n, the height h of the BST can vary greatly, depending on the order in which nodes are inserted. It can be as little as log(n) or as great as n, so the actual runtimes of the main BST operations will track to the height of the tree.