A:
graph TB
linkStyle default stroke:red
A((5))-->B((4))
A-->C((7))
B-->D((3))
B-->x1[null]
D-->E((1))
D-->x2[null]
C-->x3[null]
C-->F((9))
F-->G((8))
F-->x4[null]The height of the tree is 3, so choice a is correct.
A:
graph TB
linkStyle default stroke:red
E((e))-->A((a))
E-->J((j))
A-->x1[null]
A-->B((b))
J-->I((i))
J-->x2[null]
B-->x3[null]
B-->D((d))
I-->G((g))
I-->x4[null]
D-->C((c))
D-->x5[null]
G-->F((f))
G-->H((h))Based on the above tree. The BSF traversal is going to add the root "e" in the queue first. Then, dequeue the node "e", and add its children "a" and "j" to the queue. Next, We dequeue the node "a", and enqueue its child "b" to the queue. Note that node "b" is the last node being enqueued before we move on to dequeue node "j", and add its child to the queue. So choice c is the correct answer.
A:
graph TB
linkStyle default stroke:red
Five((5))-->Three((3))
Five-->Seven((7))Based on the above example, to print the value in order, we have to print the subtree's left child("3") first, followed by the root node("5"), then the right child("7"). So we have to use the in-order traversal, which makes choice e correct.
A:
a)
graph TB
linkStyle default stroke:red
Three((332))-->Two((219))
Three-->x1[null]
Two-->Ten((10))
Two-->x2[null]
Ten-->OneF((153))
Ten-->x3[null]
OneF-->Eight((84))
OneF-->x4[null]
Eight-->Six((66))
Eight-->x5[null]Correct, we can build a valid tree.
b)
graph TB
linkStyle default stroke:red
Eight((802))-->x1[null]
Eight-->EightS((861))
EightS-->x2[null]
EightS-->Nine((989))
Nine-->EightSe((872))
Nine-->x3[null]Correct, we can build a valid tree.
c)
graph TB
linkStyle default stroke:red
One((121))-->Nine((9))
One-->x1[null]
Nine-->Four((4))
Nine-->Ten((107))
Ten-->OneH((100))
Ten-->x2[null]Incorrect! It is impossible to backtrack from node "107" to node "4" and then backtrack again to node "100". The path is not "consistent".
d)
graph TB
linkStyle default stroke:red
Three((332))-->x1[null]
Three-->ThreeN((393))
ThreeN-->x2[null]
ThreeN-->Four((432))
Four-->x3[null]
Four-->Eight((850))
Eight-->Five((570))
Eight-->x4[null]
Five-->FourS((465))
Five-->x5[null]
Correct, we can build a valid tree.
A:
graph TB
linkStyle default stroke:red
Star1((*))-->Plus1((+))
Star1-->Star2((*))
Plus1-->Eight1((8))
Plus1-->Plus2((+))
Plus2-->Six1((6))
Plus2-->Three1((3))
Star2-->Nine1((9))
Star2-->Plus3((+))
Plus3-->Two1((2))
Plus3-->Minus1(("-"))
Minus1-->x1[null]
Minus1-->Three2((3))By constructing the tree, we can see that only choice b that matches the correct in-order traversal of the nodes.
a) Correct! this tree is a valid binary search tree.
b) Incorrect, Node "2" should be the left child of node "3" instead of the right child.
c) Incorrect, there should not be a "NULL" node in the tree, unless it is the leaf node.
d) Incorrect, Node "4" has 3 children, where it should have only 2 children.
A:
Since you have to travel to the next node through pointers during the traversal, the runtime depends on the number of elements in the linked list instead of directly indexing to the desired element. So choice d is the correct answer.
A:
Again, Since you have to travel to the next node through pointers, the runtime depends on the number of elements in the linked list instead of directly indexing the desired element. More elements in the list mean a longer time to get to the element and vice versa. So choice e is the correct answer.