1List 4 characteristics that are common to all trees.
- Has a root
Unique path from root to every leaf
Has leaf Nodes
Each node can have 1 children - Has a root
Unique path from root to every leaf
Has leaf Nodes
Each node can have 0 or more children - Has no root
Unique path from root to every leaf
Has leaf Nodes
Each node can have 0 or more children
- Has a root
Same path from root to every leaf
Doesn't have leaf Nodes
Each node can have 0 or more children
2If a node of an array-based binary tree is at index 4. What is the index of it's right child?
3What additional constraint does a binary tree have over a regular tree?
- A binary tree node can have infinity children
- A binary tree node can have at most 1 children.
- A binary tree node can have at most 3 children.
- A binary tree node can have at most 2 children.
4What additional constraints does a Binary Search Tree have over a binary tree?
All nodes to the right are greater than then node, all nodes to the left are less than the node.
5What are the 3 cases for deleting from a binary search tree?
Case 1 [A] no children
Case 2 [B] 1 child or subtree
Case 3 [C] 2 children or subtrees
6In a binary expression tree:
- A leaf node contains a OPERATOR
A non-leaf node contains a OPERAND - A leaf node contains a OPERATOR
A non-leaf node contains a OPERATOR - A leaf node contains a OPERAND
A non-leaf node contains a OPERATOR - A leaf node contains a OPERAND
A non-leaf node contains a OPERAND
7Given the following binary tree structure:
10
/ \
20 30
/ \ /
40 50 60
What will be the resulting array when converted using the "2i + 1" and "2i + 2" indexing rule?
- [10, 20, 30, 40, 50, 60]
- [10, 30, 20, 40, 50, 60]
- [10, 20, 30, 50, 40, 60]
- [10, 20, 30, 40, 60, 50]
8 1
/ \
2 3
/ \
4 5
What is the index of the left child of node 2 in the array representation?
9You are given a binary tree that is skewed to the left, represented as:
5
/
4
/
3
/
2
/
1
What will be the resulting array when converted using the "2i + 1" and "2i + 2" indexing rule?
- [5, 4, 0, 3, 0, 2, 0, 1]
- [5, 0, 0, 4, 0, 3, 0, 2, 0, 1]
- [5, 4, 3, 2, 1]
- [5, 4, 0, 0, 3, 0, 0, 2, 0, 1]
10What is the pseudocode for a function that converts a binary tree to an array using the "2i + 1" and "2i + 2" indexing rule? Which of the following snippets correctly initializes the array?
- int[] array = new int[2 * n];
- int[] array = new int[n];
- int[] array = new int[n + 1];
- int[] array = new int[2 * n + 1];
11 7
/ \
8 9
/ \
10 11
If you create an array using the "2i + 1" and "2i + 2" rule, what will the array look like?
- [7, 8, 9, 10, 11]
- [7, 9, 8, 10, 11]
- [7, 8, 9, 11, 0, 0, 10]
- [7, 8, 9, 11, 10]
12 After removing node 8 from the binary tree:
7
/ \
8 9
/ \
10 11
How would the array look after the conversion to an array using the "2i + 1" and "2i + 2" rule?
- [7, 8, 9, 10, 11]
- [7, 9, 8, 11, 10]
- [7, 9, 0, 10, 11]
- [7, 9, 0, 11, 10]
13What is the In Order Traversal
- LEFT
ROOT
RIGHT - ROOT
LEFT
RIGHT - LEFT
RIGHT
ROOT
14What is the Pre Order
- ROOT
LEFT
RIGHT - LEFT
RIGHT
ROOT - LEFT
ROOT
RIGHT