invert_tree_fsharp.md

Invert Binary Tree in F#

An inverted Binary Tree is a Binary Tree with left and right children of all non-leaf nodes interchanged.

type Node =
  { Value: int
    Left: Node option
    Right: Node option }

let root =
  { Value = 9
    Left =
      Some
        { Value = 3
          Left = Some { Value = 1; Right = None; Left = None }
          Right = Some { Value = 4; Right = None; Left = None } }
    Right = Some { Value = 5; Left = None; Right = None } }

let printDfs prefix node =
  let rec dfs (stack: Node list) result =
    match stack with
    | [] -> result
    | head :: tail ->
        dfs
          (([ head.Left; head.Right ] |> List.choose id) @ tail)
          (head.Value :: result)
  
  dfs [ node ] [] |> List.rev |> printfn "%s\n%A\n" prefix

// FIXME: implement invertion of the tree
let invertTree (root: Node) = root

root 
|> printDfs "original" // [9; 3; 1; 4; 5]


root 
|> invertTree 
|> printDfs "inverted" // [9; 5; 3; 4; 1]

• Implement invertion of the tree
• What is the runtime complexity?
• What is the memory complexity?
• Will it stack overflow on very large trees?

solution (click to expand)

The easiest solution.

let invertTree (root: Node) =
  let rec invert =
    function
    | None -> None
    | Some n ->
        Some
          { Value = n.Value
            Left = invert n.Right
            Right = invert n.Left }

  invert (Some root) |> Option.get

root 
|> invertTree 
|> printDfs "inverted simple" // [9; 5; 3; 4; 1]

• Runtime complexity: O(n)
• Memory complexity: O(n)
• Will it stack overflow? Yes.

It will stack overflow on very deep trees. Try it with this tree

let root =
  [ 1 .. 305000 ]
  |> List.fold (fun prev i -> Some { Value = i; Left = None; Right = prev }) None
  |> Option.get

another solution (click to expand)

We can do a breadth-first search, and with the leaf nodes first, swap left and right until we reach the root.

type Queue<'a> = Queue of list<'a> * list<'a>

module Queue =
  let empty = Queue([], [])
  let enqueue (Queue (front, back)) x = Queue(front, x :: back)

  let rec dequeue =
    function
    | Queue ([], []) -> None, Queue([], [])
    | Queue (x :: front, back) -> Some x, Queue(front, back)
    | Queue ([], back) -> dequeue (Queue(List.rev back, []))

let rec bfs result queue =
  match Queue.dequeue queue with
  | None, _ -> result
  | Some node, queue ->
      bfs
        (node :: result)
        ([ node.Right; node.Left ]
         |> List.choose id
         |> List.fold Queue.enqueue queue)

let rec swap computed nodes =
  match nodes with
  | [] -> computed
  | head :: tail ->
      swap
        (Map.add
          (Some head)
          { Value = head.Value
            Left = Map.tryFind head.Right computed
            Right = Map.tryFind head.Left computed }
          computed)
        tail

let invertTree2 root =
  root
  |> Queue.enqueue Queue.empty
  |> bfs []
  |> swap Map.empty
  |> Map.find (Some root)

root
|> invertTree2
|> printDfs "inverted BFS-SWAP"

• Runtime complexity: O(n log n) because Map.add is O(log n)
• Memory complexity: O(n)
• Will it stack overflow? No.

another solution (click to expand)

continuation passing style (CPS)

let invertTree3 root =
  let rec invert node (continuation: Node option -> Node option) =
    match node with
    | None -> continuation None
    | Some n ->
        invert n.Left (fun left ->
            invert n.Right (fun right ->
                continuation (Some({ Value = n.Value; Left = right; Right = left }))))

  invert (Some root) id |> Option.get


root 
|> invertTree3 
|> printDfs "inverted CSP"

• Runtime complexity: O(n)
• Memory complexity: O(n)
• Will it stack overflow? No.

another solution (click to expand)

continuation passing style (CPS) with computation expression

type ContinuationBuilder() =
  member this.Return(x) = (fun k -> k x)
  member this.Bind(m, f) = (fun k -> m (fun a -> f a k))
  member this.Delay(mk) = fun c -> mk () c

let cps = ContinuationBuilder()

let invertTree4 root =
  let rec invert node =
    cps {
      match node with
      | None -> return None
      | Some n ->
          let! left = invert n.Left
          let! right = invert n.Right
          return Some { Value = n.Value; Right = left; Left = right }
    }

  invert (Some root) id |> Option.get

root 
|> invertTree4 
|> printDfs "inverted CSP CE

• Runtime complexity: O(n)
• Memory complexity: O(n)
• Will it stack overflow? No.

another solution (click to expand)

open System.Collections.Immutable

let rec bfs result (queue: ImmutableQueue<Node>) =
  if queue.IsEmpty then
    result
  else
    let queue, node = queue.Dequeue()
    let queue = if node.Right.IsSome then queue.Enqueue(node.Right.Value) else queue
    let queue = if node.Left.IsSome then queue.Enqueue(node.Left.Value) else queue
    bfs (node :: result) queue

let rec swap computed (nodes: Node list) =
  match nodes with
  | [] -> computed
  | head :: tail ->
      swap
        (Map.add
          (Some head)
          { Value = head.Value
            Left = Map.tryFind head.Right computed
            Right = Map.tryFind head.Left computed }
          computed)
        tail

(ImmutableQueue.Create(root))
|> bfs []
|> swap Map.empty
|> Map.find (Some root)
|> printDfs "inverted"

• Runtime complexity: O(n log n) ??
• Memory complexity: O(n)
• Will it stack overflow? No.

another solution (click to expand)

let rec invertTree node =
  lazy
    (match node with
     | Some n ->
         Some
           { Value = n.Value
             Left = (invertTree n.Right).Force()
             Right = (invertTree n.Left).Force() }
     | None -> None)

Some root
|> invertTree
|> fun x -> x.Force()
|> Option.get
|> printDfs "inverted

• Runtime complexity: O(n)
• Memory complexity: O(n)
• Will it stack overflow? Yes! .Force() call stack overflows