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