ℹ️ Select 'Choose Exercise', or randomize 'Next Random Exercise' in selected language.

Choose Exercise:
Timer 00:00
WPM --
Score --
Acc --
Correct chars --

OCaml: Binary Search Tree Insertion (Recursive)

OCaml

Goal -- WPM

Ready
Exercise Algorithm Area
1(* OCaml implementation of Binary Search Tree (BST) insertion using recursion. *)

2

3(* Define the structure for a BST node. *)

4type 'a bst_node =

5| Empty

6| Node of 'a * 'a bst_node * 'a bst_node

7

8(* Helper function to create a new node. *)

9let create_node value left right = Node (value, left, right)

10

11(* Function to insert a value into a BST. *)

12(* If the value already exists, it is not inserted to maintain uniqueness. *)

13let rec insert value tree =

14match tree with

15| Empty ->

16(* Base case: If the tree is empty, create a new node with the value. *)

17create_node value Empty Empty

18| Node (node_value, left, right) ->

19(* Recursive step: Compare the value to be inserted with the current node's value. *)

20if value < node_value then

21(* If the value is smaller, insert into the left subtree. *)

22let new_left = insert value left in

23create_node node_value new_left right

24else if value > node_value then

25(* If the value is larger, insert into the right subtree. *)

26let new_right = insert value right in

27create_node node_value left new_right

28else

29(* If the value is equal, do not insert (maintaining uniqueness). *)

30tree

31

32(* Helper function to perform an in-order traversal to verify BST structure. *)

33let rec inorder_traversal tree acc =

34match tree with

35| Empty -> acc

36| Node (value, left, right) ->

37let left_acc = inorder_traversal left acc in

38let current_acc = value :: left_acc in

39inorder_traversal right current_acc

40

41(* Example Usage: *)

42let () =

43(* Initialize an empty BST *)

44let empty_tree : int bst_node = Empty in

45

46(* Insert elements *)

47let tree1 = insert 5 empty_tree in

48let tree2 = insert 3 tree1 in

49let tree3 = insert 7 tree2 in

50let tree4 = insert 2 tree3 in

51let tree5 = insert 4 tree4 in

52let tree6 = insert 6 tree5 in

53let tree7 = insert 8 tree6 in

54

55(* Attempt to insert a duplicate *)

56let tree_with_duplicate = insert 4 tree7 in

57

58(* Verify the structure using in-order traversal *)

59let sorted_list = inorder_traversal tree_with_duplicate [] in

60Printf.printf "BST after insertions: %s\n" (String.concat ", " (List.map string_of_int sorted_list));

61

62(* Edge case: inserting into an empty tree *)

63let single_node_tree = insert 10 Empty in

64let single_node_list = inorder_traversal single_node_tree [] in

65Printf.printf "BST with single node: %s\n" (String.concat ", " (List.map string_of_int single_node_list));

66

67(* Edge case: inserting a value smaller than all existing *)

68let smaller_val_tree = insert 1 Empty in

69let smaller_val_list = inorder_traversal smaller_val_tree [] in

70Printf.printf "BST after inserting smaller value: %s\n" (String.concat ", " (List.map string_of_int smaller_val_list));

71

72(* Edge case: inserting a value larger than all existing *)

73let larger_val_tree = insert 100 Empty in

74let larger_val_list = inorder_traversal larger_val_tree [] in

75Printf.printf "BST after inserting larger value: %s\n" (String.concat ", " (List.map string_of_int larger_val_list));
Algorithm description viewbox

OCaml: Binary Search Tree Insertion (Recursive)

Algorithm description:

This OCaml code defines and implements insertion into a Binary Search Tree (BST) using a recursive approach. A BST is a data structure where each node has at most two children, referred to as the left child and the right child, with the property that the left child's value is less than the parent's value, and the right child's value is greater than the parent's value. This structure allows for efficient searching, insertion, and deletion of elements. It's fundamental in many computer science applications, including databases and symbol tables.

Algorithm explanation:

The provided OCaml code implements recursive insertion into a Binary Search Tree (BST). The `bst_node` type is defined as either `Empty` or a `Node` containing a value and two child BSTs. The `insert` function takes a value and a tree, returning a new tree with the value inserted. The base case for the recursion is when the tree is `Empty`; in this scenario, a new `Node` is created with the given value and two `Empty` children. For a non-empty `Node`, the function compares the `value` to be inserted with the `node_value`. If `value` is smaller, it recursively calls `insert` on the `left` subtree. If `value` is larger, it recursively calls `insert` on the `right` subtree. If `value` is equal to `node_value`, the tree remains unchanged to ensure unique values. The `create_node` helper constructs a new node, ensuring immutability by returning a new tree structure rather than modifying existing nodes. The time complexity for insertion in a balanced BST is O(log n), where n is the number of nodes. However, in the worst case (a skewed tree), it can degrade to O(n). The space complexity is O(log n) for a balanced tree due to the recursion stack, and O(n) for a skewed tree. Edge cases like inserting into an empty tree, inserting smaller/larger values than existing ones, and handling duplicates are addressed.

Pseudocode:

type bst_node:
  Empty
  Node(value, left_child, right_child)

function insert(value, tree):
  if tree is Empty:
    return Node(value, Empty, Empty)
  else:
    node_value = tree.value
    left_child = tree.left_child
    right_child = tree.right_child

    if value < node_value:
      new_left_child = insert(value, left_child)
      return Node(node_value, new_left_child, right_child)
    else if value > node_value:
      new_right_child = insert(value, right_child)
      return Node(node_value, left_child, new_right_child)
    else:
      // Value already exists, return the original tree
      return tree