# Is my mathematical representation of search in binary search tree correct?

You are given the root of a binary search tree (BST) and an integer val.

Find the node in the BST that the node's value equals val and return the subtree rooted with that node. If such a node does not exist, return null.

I have came up with a recursive solution in python, but I also want to document down the mathematical representation. I came up with the following, am I correct notation wise?

$$f(v, x) = \begin{cases} \emptyset & \text{if } v = \emptyset \\ f\Big(\ell(v), x\Big) & \text{if } g(v) > x \\ f\Big(r(v), x\Big) & \text{if } g(v) < x \\ v & \text{otherwise} \end{cases}$$

where

• $$\emptyset$$ is the empty tree, or None in Python
• $$v$$ is a node in the tree
• $$\ell(v)$$ is the left child of $$v$$
• $$r(v)$$ is the right child of $$v$$
• $$g(v)$$ is the value of node $$v$$, and $$x$$ is the target value to search for.

In this formulation, the function $$f$$ takes two arguments: a node $$v$$ and a target value $$x$$. The function $$\ell(v)$$ returns the left child of the node $$v$$ and $$r(v)$$ returns the right child. Depending on the comparison of the value of node $$v$$ and the target $$x$$, the function $$f$$ recursively calls itself on either the left child or the right child of $$v$$. If $$v$$ is empty, it returns $$\emptyset$$. If the value of node $$v$$ equals the target $$x$$, it returns $$v$$ itself. This function could be seen as a search algorithm on a binary tree.

• This seems quite correct. $\text{otherwise}$ is also $v\ne\emptyset\land g(v)=x$.
– user16034
Jul 19, 2023 at 15:08
• @YvesDaoust Thanks for confirming, will the notation be more confusing if I replace $\ell(v)$ and $r(v)$ with $v_{\ell}$ and $v_r$? Jul 20, 2023 at 3:44
• IMO, this is a bad idea.
– user16034
Jul 25, 2023 at 19:07

$$search(node, val) = \begin{cases} \emptyset & \text{if } node = \emptyset \\ search(node.left, val) & \text{if } node.val > val \\ search(node.right, val) & \text{if } node.val < val \\ node & \text{otherwise} \end{cases}$$