# Algorithm to find the saddle point in a Binary tree

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)

• 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$. Oct 19 at 20:55
• (With a (binary) max heap, take any node.) Oct 20 at 5:46
• @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 Oct 20 at 15:33

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.