i am constructing the operations of `binary search tree`

in OCaml.

```
type ('a, 'b) bst =
| Node of 'a * 'b * ('a, 'b) bst * ('a, 'b) bst
| Leaf;;
let rec insert k v = function
| Leaf -> Node (k, v, Leaf, Leaf)
| Node (k', v', left, right) ->
if k < k' then Node (k', v', insert k v left, right)
else if k = k' then Node (k, v, left, right)
else Node (k', v', left, insert k v right);;
let rec delete k = function
| Leaf -> Leaf
| Node (k', v, l, r) as p ->
if k < k' then Node (k', v, (delete k l),r)
else if k > k' then Node (k', v, l, (delete k r))
else
match (l, r) with
| (Leaf, Leaf) -> Leaf
| (l, Leaf) -> l
| (Leaf, r) -> r
| (_, _) ->
let Node (km, vm, _, _) = max l in
Node (km, vm, delete km l, Leaf)
```

**Can anyone tell me whether my deletion code is good enough or any improvement?**

One improvement is the case when we insert things that are in the tree, or delete things that are not in the tree. Each of these operations will duplicate the search path to that particular node. Insertion is probably not a problem since you will want to update the value of that key, but deletion would be a case where you can make an improvement. This can be solved by wrapping the function with an exception to return the original tree.

Here is what a deletion would look like for something that is not in the tree. As you recurse you create a new `Node`

with the key deleted in the correct subtree. In this particular case the delete function will recurse to a `Leaf`

then return a `Leaf`

and on each step back up the stack return a newly constructed `Node`

. This new path is represented as the blue path below. Since there is no structure to unwind the new path to the old path we re-create the search path in the result tree.

```
let at = delete x bt
```

To fix this issue, as mentioned wrap the function in an exception.

```
let delete k t =
let rec delete k = function
| Leaf -> raise Not_found
...
in
try delete k t with Not_found -> t
```

Similar Questions

I'm working through the exercises in the book Beginning Haskell. Exercise 4-8 is to make a binary search tree an instance of Functor and define fmap. This is what the tree looks like: data BinaryTre

My program is calling a member function that performs an insertion into a binary search tree with a pointer passed by reference (so that the value of the pointer is changed). However when I attempt to

I am creating a binary search tree class in c#. I am creating the class by deriving from a binary tree class because binary search tree is a kind of binary tree. So i will have most of the common meth

Having a Binary Search Tree of int create a linked list of all the integers less than a given integer x value. What I've tried? 1)brutal solution(inefficient) An inorder visit of the BST, I insert a

Consider you have Binary Search Tree, in case multiply all nodes by -1 then can anybody please let me know if its still a Binary Search Tree? Whether is it possible to write a function which converts

When programming a simple binary search tree data structure (non self-balancing), the advice most resources give when deleting a node with two children is to copy the data out of one of the left child

A friend was recently interviewed for a position at a tech company and was given 4 programming tasks. One of the tasks was to implement a Binary Search Tree class using a Linked List implementation w

Why do people use binary search trees? Why not simply do a binary search on the array sorted from lowest to highest? To me, an insertion / deletion cost seems to be the same, why complicate life with

When removing a node with two children in a binary search tree, how many times can the recursive removal of the child node be called?

As you know how avl should be balanced after deletion of a node, I'll get to point. For starting, Im considering deleting a node with no children. For Example a Tree: 10 / \ 5 17 / \ / \ 2 9 12 20 \

Why the search and successor and predecessor returns -1? // BST.cpp : main project file. #include stdafx.h #include <cstdlib> #include <iostream> #define SIZE 10 using namespace std; st

I want to implement a binary tree such that it does not include duplicates. Here's my insert() method. public BinaryNode insert(BinaryNode node, int x) { if (node == null) { node = new BinaryNode(x);

I have programmed a binary search tree with method Add(). But it is not working. When I add number to the tree, root is still empty. Why? EDIT: Code on pastebin, here I am havig some problems with dis

I am trying to implement a binary search tree in python, but I can't find a solution for delete. If the item is in a leaf, that is simple, but what if the item I want to delete has 2 children which al

In preparation for the data structures midterm, the professor gave us last year's test, one question which deals with re-arranging an example tree into a complete binary search tree. I've tried severa

I'm learning Data Structures & Algorithms now. My lecture notes have an implementation of a binary search tree which is implemented using a recursive method. That is an elegant way, but my questio

well i was creating a binary search tree using this code..as far as i as see using this code i find it to be correct but some how its creating error i dont know why #include<stdio.h> #include<

I need to create a recursive method that takes as a parameter the root node of a binary search tree. This recursive method will then return the int value of the total number of nodes that have one lef

http://pastebin.com/dN9a9xfs That's my code to print out the elements of a binary search tree. The goal is to display it in level order, with slashes connecting the parent to each child. So for instan

Im writing a binary search tree and i want to include a parent pointer. The way I have it now is that the parent reference is a node. so for example my getParent() returns a node rather than a value.

others say that for making a binary search tree with an array of {3,7,1,90,45,67,54,23,...} it is good to work with TreeSet.but my code below will throw an exception and I don't know why? my array lis

Why is the worst case big-O for inserting N items into an empty binary search tree n^2? there are no balance checks.

I'm trying to insert an item into a binary search tree, but I'm getting an error and I can't understand why. If I try to run: (insert 11 '(5 '() '())) The error is: . . >: contract violation expec

So I've stumped on this current problem I'm working on. Basically, I need to add an element to my array based binary search tree. According to my text it is similar to the compareTo method. I'm not ev

I have a problem with insertion in Binary search tree in C. I have the following definition of a binary tree(please ignore line numbers): 40 struct WordBT 41 { 42 char *term; 43 struct WordBT *right;

I am having trouble outputting a binary search tree. I have to build the tree, and then place all the doubles from the tree in order into a vector, and then output that vector in order. The problem I

I need a general formula to calculate the minimum height of the binary tree and the maximum height of the binary tree. (not the binary search tree)

I'm working on a problem for class I'm stuck on. It involves adding a methods to the Binary Search Tree found here: http://algs4.cs.princeton.edu/32bst/BST.java.html I need to develop an iterative cei

I'm using OCaml. I have type: type 'a bt = Empty | Node of 'a * 'a bt * 'a bt;; Also I have example BST: let tree = Node(1,Node(2,Node(4,Empty,Empty),Empty),Node(3,Node(5,Empty,Node(6,Empty,Empty)),

Note: I've included the code for the insert in case that is where my error lies. I'm having trouble removing nodes in my binary search tree. I ran this through eclipse and the node's pointers seem t

I've given the result of in-order traversal of a binary tree (not binary search tree) as: E, D, B, A, G, F, H, C Now I've to find out the result of the post-order traversal of the same tree for which

I'm trying to fill in a binary search tree with a text file, but i'm having alot of trouble implementing my insert function. Am i reading the input correctly or is it my code? Code for reading file: i

I'm having trouble writing code to determine if certain data is present in my tree, this is the BinaryTreeNode class class BinaryTreeNode { public: Data * nodeData; BinaryTreeNode * left; BinaryTreeNo

What is the benefit of a binary search tree over a sorted array with binary search? Just with mathematical analysis I do not see a difference, so I assume there must be a difference in the low-level i

I am reading through the binary tree delete node algorithm used in the book Data Structures and Algorithms: Annotated Reference with Examples on page 34 , case 4(Delete node which has both right and l

I have constructed a binary search tree using a text file that is read in by the main function. The resulting tree contains the words of the text file, with a count so that the same word is not insert

I want to find minimum value in a Binary Search Tree. I have written below code. But when i call the function from main and I pribt the return value, it is printing as 0 always. cal you please help. i

I am reading a book about removing a node from a binary search tree right now and the procedure described in the book seems unnecessarily complicated to me. My question is specifically about removing

What is the difference between binary search and binary search tree? Are they the same? reading the internet it seams the second is only for trees(up to 2 children nodes) and binary search doesn't fol

I'm working through a Binary search tree tutorial. And I find this function destroy_tree(node* leaf). Its behaviour worries me - I can't imagine how the call stack looks like, can you explain it to

I'm having issues implementing my breadth first traversal for my binary tree. I keep getting a class cast exception at these two lines: if(node.left != null) queue.offer(node.left); if(node.right !=

I have been plugging away at a Binary Search Tree implementation for a few days now and I am to the point where I know that my root is being populated through the use of my 'insert()' (I can see this

I was studying Binary Trees. And I found this code for the insertion of a node in the tree. Here root is a pointer variable of structure type in a class TreeType as a private member. In this fun

I am unsure as to what I need to do to search for a string stored in a binary tree. I have the search method written but I don't quite understand what to pass it. I need to search for the string befor

can a node be inserted in a non leaf position in a binary search tree ? for eg. if we have the following set of numbers to be arranged as a binary serach tree :- 20.,17,15,19,23,25.... so there is mo

I am learning c++ and data structures I have implemented binary search tress can any body tell what is the issue in this code I am getting root pointer as null. Basically unable to create a tree. My f

so i need to implement a member function, pre-order and inorder traversal of a binary search tree using recursion. i'm having trouble implementing all three, since they're coming out with the wrong ou

Say I have a binary tree with the following definition for a node. struct node { int key1 ; int key2 ; } The binary search tree is created on the basis of key1. Now is it possible to rearrange the

Which would take longer? print all items stored in a binary search tree in sorted order or print all items stored in a hash table in sorted order. It would take longer to print the items of a hash ta

Is there a built in binary search tree in .NET 4.0, or do I need to build this abstract data type from scratch?