binary tree visiting algorithms

binary-tree-roadtrip.ml

type 'a binary_tree = Leaf | Node of 'a * 'a binary_tree * 'a binary_tree;;

let visit_binary_tree tree (visiting_function:'a binary_tree -> 'a list) :'a list = match tree with
| Leaf -> []
| Node (_, _, _) -> visiting_function tree;;

(*
    1
   / \
  2   3
 / \   \
4   5   6
*)
let t = Node(1, Node(2, Node(4, Leaf, Leaf), Node(5, Leaf, Leaf)), Node(3, Leaf, Node(6, Leaf, Leaf)));

let get_root_node_value (tree: 'a binary_tree) : int = match tree with
| Leaf -> 0
| Node (v, _, _) -> v;;

let rec symmetric_visit (tree: 'a binary_tree) : 'a list = match tree with
| Leaf -> []
| Node (v, left_tree, right_tree) -> symmetric_visit (left_tree) @ [v] @ symmetric_visit (right_tree);;

let rec preorder_visit (tree: 'a binary_tree) : 'a list = match tree with
| Leaf -> []
| Node (v, left_tree, right_tree) -> [v] @ symmetric_visit (left_tree) @ symmetric_visit (right_tree);;

let rec postorder_visit (tree: 'a binary_tree) : 'a list = match tree with
| Leaf -> []
| Node (v, left_tree, right_tree) -> symmetric_visit (left_tree) @ symmetric_visit (right_tree) @ [v];;