(Solved): Consider a binary search tree that stores a list of values. In addition to a value from the list, e ...

Consider a binary search tree that stores a list of values. In addition to a value from the list, each tree node also stores an integer value called subtreeCount that is the number of nodes in the subtree rooted at that node (including that node). Given an existing binary search tree without any subtreeCount values computed yet, what type of tree traversal would you use to assign all the subtreeCount values? pre-order: process parent before children in-order: process in the order left child, parent, right child post-order: process children before parent depth-first search Question 46 \( 1 \mathrm{pts} \) What is the overall runtime of the traversal algorithm above to assign the subtreeCount to every node in an existing BST? O(log n) \( O(n) \) \( O(n \log n) \) \( O\left(n^{\wedge} 2\right) \)