Binary Trees

Question 1

types of trees

Answer 1

Ordered tree (implies rooted)

Binary tree (implies ordered)

m-ary tree (usually ordered)

Labeled and/or search tree

R-B Tree

AVL Tree

Question 2

What does each node of a binary tree consist of?

Answer 2

• A value (some sort of data item) • A reference or pointer to a left child (may be null), and A reference or pointer to a right child (may be null)

Question 3

If a binary tree is not empty it has a…?

Answer 3

root node

Question 4

A node without a left or right child is called a…?

Answer 4

leaf

Question 5

What is the order of a tree?

Answer 5

number of nodes

Question 6

What is the size of a tree?

Answer 6

number of edges, order -1

Question 7

What is the depth of a node?

Answer 7

distance from root to the node where root to root is depth of 0

Question 8

What is the height of a tree?

Answer 8

depth of the deepest node

Question 9

For the following what is the order, size, depth (from a⇒a, a⇒e, a⇒k) and height

Answer 9

order = 12

size = 11

depth = 0, 2, 3 respectively

height = 4

Question 10

When is an m-ary tree balanced?

Answer 10

When the heights of the subtrees of every node never differ by more than one.

Question 11

When is a m-ary tree full?

Answer 11

full if every node has either 0 or m children

Question 12

When is a m-ary tree complete?

Answer 12

complete if all levels have no missing siblings/cousins, except possibly the last (partial left-filled) level

Question 13

pre, post and in order

Answer 13

Question 14

what is it called to o visit nodes from top-to-bottom and left-to-right

Answer 14

level-order traversal

Question 15

Average height for BST, R-B tree and AVL trees?

Answer 15

BST: 4 lg n

R-B: 2 lg n

AVL: 1.5 lg n

Question 16

What are B-Trees used for?

Answer 16

• A B-tree implements the table API but used for external/slow devices such as disks (or cloud)

Question 17

What is a B-Tree?

Answer 17

A B-tree of order m is an m-ary tree such that:

• the root is either a leaf or it has between 2 and m children;
• each nonleaf node (except possibly the root) has between

dm/2e and m children inclusive;

• each nonleaf node with µ children has µ − 1 keys;
• all leaves are at the same depth;

Question 18

What is a red-black tree?

Answer 18

A red-black tree is a binary search tree such that every node is colored either red or black and every non-leaf node has two children. In addition, it satisfies the following properties:

• the root is black;
• all children of a red node must be black;
• every path from the root node to a leaf must contain the same number of black nodes.

Question 19

If every path from the root to a leaf contains b black nodes then how many black nodes are in the tree?

Answer 19

at least 2b − 1 black nodes

Question 20

What is the height of an AVL tree with n nodes?

Answer 20

Θ(log n) (AVL trees are more rigidly balanced than red-black trees so good for applications with more prominent search-only operations)

Question 21

What technique is used to make sure worst case does not occur in BST?

Answer 21

balancing

Question 22

What is an AVL tree?

Answer 22

An AVL tree is a binary search tree with the additional balance property that the tree is balanced

Question 23

What is a BST?

Answer 23

A binary search tree (BST) is a binary tree that satisfies the following ordering relation: for every node ν in the tree, the values of all the keys in the left subtree are smaller than (or equal, if duplicates allowed) to the key in ν and the values of all the keys in the right subtree are greater than the key in ν.

Left subtree has smaller valued nodes then right subtree

Question 24

The search, retrieval, update, insert and remove operations in a BST all take what time?

Answer 24

O(h) in the worst case, where h is the height of the tree