0
$\begingroup$

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.

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

1 Answer 1

0
$\begingroup$

It is correct, but it could be made more readable.

$$ 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} $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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