Ranter
Join devRant
Do all the things like
++ or  rants, post your own rants, comment on others' rants and build your customized dev avatar
Sign Up
Pipeless API
From the creators of devRant, Pipeless lets you power realtime personalized recommendations and activity feeds using a simple API
Learn More
Comments

If we say that in functional programming has to be a function, then it could be a function which given "right" returns the right branch, and given "left" returns the left branch. But honestly I don't know. There are probably multiple ways

In Haskell you can do it with data types. Something along
data Tree a = Leaf a  Branch a 

@Flamestro yup, you're correct, that would work for a general binary tree (though you forgot the type var on the definition side). To make it a BST you need to define insert and search.
data BST a = Node a (BST a) (BST a)  Leaf
Insert and search are fairly easy, assuming lessthan corresponds to left
insert val Leaf = Node val Leaf Leaf
insert val (Node nodeVal left right)
 val < nodeVal = Node nodeVal (insert val left) right
 otherwise = Node nodeVal left (insert val right)
search val Leaf = false
search val (Node nodeVal left right)
 val == nodeVal = true
 val < nodeVal = search val left
 otherwise = search val right
Logic: inserting into a leaf means making a node with the value and two leaves; into a node means inserting either to the left or right subtrees of the node.
if you search a leaf your value is not in the tree, if you search a node either it has the value you want, or the value is possibly in the left or right subtrees. 
However this kind of definition is a feature of algebraic data types (ADTs), not the more general class of functional programming (which basically just means that functions are values).
If you have impure FP (or FP with controlled side effects like Haskell's ST and IO monads) then data structures look just like their counterparts in other languages.
Pure FP data structures however generally means that you return a whole new data structure after an update operation, i.e. the old data structure isn't destroyed so it's still around, i.e. the data structure is _persistent_ (in practice this is terrible for efficiency so implementations generally optimize via value sharing or something).
So a simple (and terrible) way to do it in JS would be to make a regular BST and have insert() return a whole new copy of the tree with the value inserted, so you avoid destructive updates. Check out immutable.js for a better implementation (I think) (don't know much about JS, sorry) 
opened devrant in browser to type this and wow the site is a lot better than the app
type tree =  Empty  Node of int * tree * tree;;
let _t = (*make a tree*);;
let rec find key tree =
match tree with
 Empty > false
 Node (k, l, r) > if k = key then true else find key l or find key r;; 
Woaw woaw woaw guys, I opened yo see what has happened to rant I posted and omg.
First of all, I don't know haskell ðŸ˜…ðŸ˜‚.
Can any one tell me in JS or something ðŸ˜…ðŸ˜…ðŸ˜…
Related Rants
I am wondering how a #FunctionalProgramming based implementation of a Binary Search Tree would look like?
Has anyone tried it?
question
javascript
algorithms
functional programming
data structures
js