# Binary Trees Flashcards

types of trees

Ordered tree (implies rooted)

Binary tree (implies ordered)

m-ary tree (usually ordered)

Labeled and/or search tree

R-B Tree

AVL Tree

What does each node of a binary tree consist of?

• 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)

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

root node

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

leaf

What is the order of a tree?

number of nodes

What is the size of a tree?

number of edges, order -1

What is the depth of a node?

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

What is the height of a tree?

depth of the deepest node

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

order = 12

size = 11

depth = 0, 2, 3 respectively

height = 4

When is an m-ary tree balanced?

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

When is a m-ary tree full?

full if every node has either 0 or m children

When is a m-ary tree complete?

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

pre, post and in order

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

level-order traversal

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

BST: 4 lg n

R-B: 2 lg n

AVL: 1.5 lg n