Suppose you have an unordered tree with n nodes. And suppose youre searching for a node with the value k . This should take the longest when k isnt in the tree. Briefly justify your answers.

3. (6 points- Correctness) Tree Search: (a) Suppose you have an unordered tree with n nodes. And suppose you're searching for a node with the value k. This should take the longest when k isn't in the tree. Briefly justify your answers. (BFS) If k isn't in the tree, how long does it take breadth first search to tell you that? (DFS) If k isn't in the tree, how long does it take depth first search to tell you that? (b) Iterative deepening DFS (IDDFS) is a tree search strategy "[...] in which a depth-limited version of depth-first search is run repeatedly with increasing depth limits until the goal is found." It's often used in game tree exploration, e.g. solving chess, as it allows for more efficient exploration of the space of possibilities, especially at earlier levels of the tree. Fill in the blanks below to implement IDDFS. class TreeNode public: TreeNodeleft, right: T value int height; I/ root node stores tree height; a sinale node tree has height o bool find (const TreeNode T& value) * root, const if (rootllptr) return false: for (int max level-0 max_level++) if (iddfs (root, value, max_level)) return true: return false; bool iddfs (const TreeNode