0
$\begingroup$

How to find a saddle point in a binary tree. where saddle point is a node in a tree whose value = min(the node and all its ancestors) = max ( the node and all its descendants)

$\endgroup$
3
  • 3
    $\begingroup$ Such a node might not exist. For example consider tree with $3$ vertices: the root and its two children. The value of the root is $1$ and the value of the children are $2$ and $3$. $\endgroup$
    – Steven
    Oct 19 at 20:55
  • $\begingroup$ (With a (binary) max heap, take any node.) $\endgroup$
    – greybeard
    Oct 20 at 5:46
  • $\begingroup$ @Steven In case there is no node, we could retrieve that information. So if there is a saddle point, then the algorithm should output it; otherwise could return null, indicating there is no saddle point. I am not sure how to begin finding an algorithm for this $\endgroup$
    – rohit
    Oct 20 at 15:33
0
$\begingroup$

Here is a sketch.

Given a node $u$, let $p_u,\ell_u,r_u,v_u$ denote its parent, it's left children, it's right children, and the value stored in $u$, respectively. Let $m(u)$ denote the minimum among all the values stored in the ancestors of $u$ ($u$ is an ancestor of itself). Let $M(u)$ denote the maximum among all the values stored in all the descendants of $u$ ($u$ is a descendant of itself).

Notice that $m(u) = \min\{v_u, m(p_u)\}$ and that $M(u)=\max\{ v_u, M(\ell_u), M(r_u) \}$ and hence all values $m(\cdot)$ can be computed in linear time by a preorder visit, while all values $M(\cdot)$ can be computed in linear time by postorder visit.

Once you know $m(u)$ and $M(u)$ for a node $u$, you can check whether $u$ is a saddle. This should be more than enough to get you started. You can fill in the other details by yourself.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.