Skip to content

Instantly share code, notes, and snippets.

@ntreu14
Created August 8, 2019 20:57
Show Gist options
  • Save ntreu14/e2f944fa89b18a39cd14749dc69885c3 to your computer and use it in GitHub Desktop.
Save ntreu14/e2f944fa89b18a39cd14749dc69885c3 to your computer and use it in GitHub Desktop.
Find height of a binary tree
type 'a Node =
| Leaf of 'a
| Group of ('a Node * 'a Node)
let findTreeHeight tree =
let rec aux tree counter =
match tree with
| Leaf _ -> counter
| Group (left, right) ->
let leftTreeHeight = aux left (counter + 1)
let rightTreeHeight = aux right (counter + 1)
System.Math.Max (leftTreeHeight, rightTreeHeight)
aux tree 0
(*********** Test Tree with height 3
Group
/ \
Group Group
/ \ / \
Leaf (1) Group Leaf (2) Leaf (3)
/ \
Leaf (5) Leaf (10)
*)
let tree =
Group (Group (Leaf 1, Group ((Leaf 5), Leaf 10)), Group (Leaf 2, Leaf 3))
printfn "%d" <| findTreeHeight tree
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment