Question $5$: You are given a complete binary tree $($i$.$e$.,$ all leaves are at the same level and

the bottom level is full$).$ The levels are numbered $0$; $1$; $2$; : : : ; d $1$ and the number n of

nodes satises n $=2$d $1.$ Each node u in this tree stores an integer value$($u$).$

$2$

$3$

$4$

$2$

$7$

$6$

$75$

$1$

$24$

$4335$

$2$

A node u is called a local minimum if value$($u$)$ is less than or equal to the values in its

neighboring nodes. In the example above, all local minima are colored red.

Describe a recursive algorithm that returns, in O$($log n$)$ time, a local minimum in this

tree.

You may describe your algorithm in plain English or in pseudocode. Justify the correct$-$

ness of your algorithm and explain why the running time is O$($log n$).$ You may use any result

that was proven in class.