Binary Trees / Binary Search Trees: Q1. Depth first traversal of a binary tree i
ID: 3716950 • Letter: B
Question
Binary Trees / Binary Search Trees:
Q1. Depth first traversal of a binary tree is the same as ___ order traversal. (pre, in, or post) (1pt)
Q2. When we add a new node to an existing binary search tree, it will always become a ____. (1pt)
Q3. When we delete a node with 2 children from a binary search tree, we replace the node with one of its' _______________. (1pt)
Q4. Give the height of each node in the following tree. (2pts)
A
/
B C
/ /
D E F
/
G
(Note: Height of a sub-tree is the height of the root of that sub-tree.
If the sub-tree is missing, its height is -1)
Q5. Is the tree in Q4 a binary tree? Why or why not? (2pts)
Q6. Is the tree in Q4 a binary SEARCH tree, why or why not? (2pts)
Explanation / Answer
ANSWER 1: In binary tree all preorder,inorder,postorder are depth first traversal so all three will come in this blank.
ANSWER 2: When we add a new node to an existing binary search tree, it will always become a leaf node.
ANSWER 3: When we delete a node with 2 children from a binary search tree, we replace the node with one of its' in this there is a situation if the node resides in left subtree then we replace with the rightmost node and if the node of 2 children reside in right subtree the we replace with right subtree leftmost node.
ANSWER 4: height of A--> -1
height of B, C -->1
height of D,E,F --> 2
height of G --> 3
ANSWER 5: Yes it is binary tree becasue it has maximum two node means left and right node.
ANSWER 6: No we can't say that it is binary search tree because in binary search tree it is necessary that left node should be less than the root node and right node should be greater than root node and here it is not clear.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.