Ordered Binary trees

Question 1

Describe Ascending/Descending in-order, post-order, pre-order

Answer 1

Ascending in order: left then parent then right 123
Descending in-order: right then parent then left 321

Ascending pre-order: parent then left then right 213
Descending pre-order: parent then right then left 231

Ascending post-order: left then right then parent 132
Descending post-order: right then left then parent 312

Question 2

Describe balance. What is a balanced tree? What is a fully balanced tree?

Answer 2

Balanced: every non-empty node has a difference of at most one in the number of items on its left and its right.

Fully balanced: Every non-empty node has an equal number of items on its left and right. Size N Depth log_2(N+1)

Question 3

What is a binary tree? What is an ordered binary tree?

Answer 3

Each node can have at most two children

A binary tree has an ordering of the tree data in it. There is a total order to the data. Ordered from left to right.

Question 4

What is the depth of a tree?

Answer 4

The number of rows
Empty: depth = 0
one node: depth = 1

Question 5

What is a tree sort?

Answer 5

Start with unsorted list. Insert into tree. Scan tree in ascending order to obtain numbers in ascending order.

Question 6

Describe the in place algorithm

Answer 6

Algorithm for balancing trees

Question 7

Describe tree data, tree data value, tree node

Answer 7

Trees consist of tree nodes. Nodes might contain data, might have children.
A non empty node contains a tree data value, left child, right child