Trees

Question 1

What is a Binary Tree?

Answer 1

A binary tree is a collection of nodes. Each node has a data value and references to two other nodes. Each node could have a left child and/or a right child.

Question 2

What is a Tree Node?

Answer 2

A tree node typically has a data component and a reference to a left child and a reference to a right child.

Question 3

When adding to a Binary Search Tree, how is the placement decided?

Answer 3

• The left child is less than the parent and the right child is greater.
• It’s always first compared to the root.

Question 4

What are the four different orders?

Answer 4

1) In-Order
2) Pre-Order
3) Post-Order
4) Rev-Order

Question 5

What’s the order for In-Order?

Answer 5

Left Data Right

Question 6

What’s the order for Pre-Order?

Answer 6

Data Left Right

Question 7

What’s the order for Post-Order?

Answer 7

Left Right Data

Question 8

What’s the order for Rev-Order?

Answer 8

Right Data Left

Question 9

What is the width in a Tree?

Answer 9

It’s the distance between two furthest leaves in the tree

does not have to do through the root

Question 10

What is the height in a Tree?

Answer 10

It’s the longest part from root to a leaf number of links from root to farthest leaf

Question 11

What is the level in a tree?

Answer 11

It’s a group of equal nodes

ex. root is level 0
(ex. the children of the root is level 1)

Question 12

How can a Binary Tree be full?

Answer 12

• Every parent has exactly two children or no children at all.
• Any levels that are not full have all nodes shifted as far left as possible

Question 13

What is a Expression Tree?

Answer 13

A binary expression tree is a binary tree in which each parent node contains an operator and each leaf contains a number.

Question 14

What is a Threaded Tree?

Answer 14

A threaded binary tree is a binary tree with an additional reference in each node that is used to point from a child back to its parent.