pathterminuspages/snippets/aboutcontactabout me

Inverting Binary Tree

29-06-2018

On reddit the other day: Some guy has written an article on how fucked startup interviews are. Luckily for me I'm not yet an applicant, but I can imagine the frustration. The article links to a Twitter account - someone has build some software that is widely used, but he still can't land a job. This is due to him failing to scrabble a solution to an Invert Binary Tree algorithm on a black board. Anyway, let's do that in Fsharp

We need to create a tree

type Tree = | Null | Node of int * Tree * Tree let tree1 = Node ( 4, Node (2,Node (1,Null,Null),Node (3,Null,Null)), Node (7,Node (6,Null,Null),Node (9,Null,Null)) )

This is difficult. tree1 is that from the challenge with height 2. Any higher might be too overwhelming to do by hand. For most manipulation with binary trees we use some sort of tree traversal algorithm. These are recursive. Let's say we want to print the tree inorder

let rec inorder root = let left = match root with | Node (_,Null,_) | Null -> Null | Node (_,lnode,_) -> inorder lnode let v = match root with | Node (v,_,_) -> printfn "%d" v | _ -> () let right = match root with | Node (_,_,Null) | Null -> Null | Node (_,_,rnode) -> inorder rnode root

This pretty much how we invert. We get

let rec invTree root = let left = match root with | Node (_,Null,_) | Null -> Null | Node (_,lnode,_) -> invTree lnode let right = match root with | Node (_,Null,_) | Null -> Null | Node (_,_,rnode) -> invTree rnode let v = match root with | Node (v,_,_) -> Node (v,right,left) | _ -> Null v

We are doing it functionally, we do not want to rely on mutable state. invTree deep copies the whole tree. And that is it. Final run

let tree1_inv = invTree tree1 inorder tree1 printfn "" inorder tree1_inv

...

CommentsGuest Name:Comment: