Binary Tree

Question 1

Mathematical Definition of a Binary Tree

Answer 1

A structure composed of zero or more nodes, each node having a label of some mathematical type (say T) called the label type

Question 2

Structure of a Binary Tree

Answer 2

A binary tree is either an empty tree (zero nodes), or a non-empty tree which consists of a root node of type T and two sub-trees, each of which is a binary tree itself. Since a non-empty binary tree is made up of binary trees, it has a recursive structure.

Question 3

Which methods does BinaryTree interface have contracts defined for?

Answer 3

T root(), T replaceRoot(T x), int height(), and void inOrderAssemble(T root, BinaryTree<T> left, BinaryTree<T> right)*
(* - inOrderAssemble not important)</T></T>

Question 4

Which interface does BinaryTree extend?

Answer 4

BinaryTreeKernel

Question 5

Which methods does BinaryTreeKernel interface have contracts defined for?

Answer 5

void assemble(T root, BinaryTree<T> left,
BinaryTree<T> right), T disassemble(BinaryTree<T> left,
BinaryTree<T> right), int size()</T></T></T></T>

Question 6

Size of a BinaryTree? How is size of a BinaryTree ‘t’ denoted in Java documentation?

Answer 6

The total number of nodes in the tree; |t|

Question 7

Height of a BinaryTree? How is height of a BinaryTree ‘t’ denoted in Java documentation?

Answer 7

The total number of nodes on the longest path from the root to an empty sub-tree of a BinaryTree; ht(t)

Question 8

Labels of a BinaryTree? How are lables of a BinaryTree ‘t’ denoted in Java documentation?

Answer 8

The set whose elements are exactly the labels of t (since it’s a set, no duplicates and no order necessary); labels(t)

Question 9

Suppose you have a BinaryTree of type Integer which has 4 as its root, 2 as the root of the left sub-tree and 3 as the root of the right sub-tree. What is the mathematical value of this BinaryTree?

Answer 9

compose (4, compose(2, empty_tree, empty_tree), compose(3, empty_tree, empty_tree))

Question 10

Which class(-es) implements the BinaryTree interface?

Answer 10

BinaryTree1

Question 11

What does the no-argument BinaryTree constructor create?

Answer 11

It ensures this = empty_tree

Question 12

How would you create a BinaryTree of String type called t using the no-argument constructor?

Answer 12

BinaryTree<String> t = new BinaryTree1<>();</String>