Properties Of Trees

Question 1

Each tree must have what?

Answer 1

Each tree must have a root node.

Question 2

Trees cannot be what?

Answer 2

Trees cannot be cyclical.

Question 3

Do nodes have to be in any particular order for you to have a tree?

Answer 3

No. Nodes may or may not be in any particular order.

Question 4

What could the value of a node be?

Answer 4

A nodes value could be any data type.

ex: string, int, boolean

Question 5

Can a nodes value link back to their parent?

Answer 5

Yes but it doesn’t have to.

Question 6

What would a simple node class contain for a tree?

Answer 6

class Node
  :name, :children 
  # name could be value 
  # children an array 
End

Question 7

What would a simple tree class contain?

Answer 7

class Tree
:root
# has a root node and root can have children nodes
End

Question 8

What determines if a tree is a binary tree?

Answer 8

• each node must less then or equal to two children nodes.

- if this is not the case you may have an n-ary tree n being the amount of children nodes for example 10-ary

Question 9

What are the properties of a leaf?

Answer 9

If node.children? == nil
node.leaf? = true.
End

Question 10

What type of tree is a binary search tree?

Answer 10

A binary search tree is a type of binary tree.

Question 11

What is unique about a binary search tree that makes it different then just a binary tree?

Answer 11

A binary search tree must fit the following ordering properties:

• Left Descendants <= Current Node < Right D.
• Sometimes not permitted to have duplicate values.
• Sometimes duplicates; but will be on the right; or possibly either side.

Question 12

A binary search tree imposes what condition?

Answer 12

Nodes.each do |node|
If node.left <= node.current_node && node.current_node < node.right_node

Left descendants <= Current node < right d

Question 13

What does a balanced tree not mean?

Answer 13

A balanced does not mean that the left and right sub-trees are of equal size. (This is a perfect tree).

*For problems with trees be sure to ask interviewer if it is balanced or not.

Question 14

What should a “balanced” tree be thought of as?

Answer 14

You could think of a “balanced tree” as a “Not terribly unbalanced tree”.
- It must be balanced enough to meet O(log n) times for insert and find.

Question 15

What are two types of balanced trees?

Answer 15

• Red-Black-Tree

- AVL Tree

Question 16

What do you call a Binary Tree in which every level of the tree is fully filled and is filled from left to right?

Answer 16

A Complete Tree

Question 17

What do you call a tree in which every node has <= 2 children.

Answer 17

Full Binary Tree

Question 18

What type of tree is both considered a Full Binary Tree and a Complete Binary Tree?

Answer 18

A Perfect Binary Tree is both full and complete!

Question 19

How could you determine if a binary tree is perfect if you have k number of levels and the number of nodes?

Answer 19

A binary tree must have 2^k-1 nodes for it to be a perfect binary tree. (K being the number of levels or degrees deep the tree is).

Question 20

What are the 3 types of Binary tree traversals?

Answer 20

1. ) In-Order
2. ) Pre-Order
3. ) Post-Order

Question 21

What is the most commonly used binary tree traversal?

Answer 21

In-Order

Question 22

When used on a Binary Search Tree In-Order traversal visits nodes in ascending or descending order?

Answer 22

When performed on a binary search tree an In-Order traversal will visit nodes in Ascending order.

Question 23

In Pre-Order traversal what order are the nodes visited?

Answer 23

First the current node then the left node and then the right node. (NLR).

Question 24

For post-order traversal what order are the nodes visited in?

Answer 24

First the current node then the children. (NLR)

Question 25

For in-order traversal, what order are the nodes traversed?

Answer 25

In-Order first visits the left node then the current node and then the right node.