CODEWITHSUNDEEP
typestreef#
Second Son
Second Son

Reputation: 1551

Three ways of traversing a binary tree recursively in Fsharp F#

I have been reading this great book Functional Programming Using F# I have just got to the chapter about finite tree and I noticed that there are three ways of traversing a tree, but I don't understand why and how they are different. Here is the code.

type BinaryTree<'a> =
    |Leaf 
    |Node of BinaryTree<'a> * 'a * BinaryTree<'a>


let rec preorder (tr:BinaryTree<'a>) : 'a list =
    match tr with
    |Leaf            -> []
    |Node(trr,x,trl) -> x:: (preorder trr) @ (preorder trl) 


let rec inorder (tree:BinaryTree<'a>) : 'a list =
    match tree with
    |Leaf -> []
    |Node(tr,x,tl) -> (inorder tr) @ [x] @ (inorder tl)

let rec postorder (tree:BinaryTree<'a>) : 'a list =
    match tree with
    |Leaf -> []
    |Node(tr,x,tl) -> (postorder tr) @ (postorder tl) @ [x]

let someTree = Node(Leaf,20,Node(Leaf,40,Node(Node(Leaf,-2,Leaf),2,Node(Leaf,0,Leaf))))

preorder someTree
inorder someTree
postorder someTree

Any Help would be welcome! :)

Upvotes: 4

Views: 1922

Answers (2)

TheInnerLight
TheInnerLight

Reputation: 12184

Look at the order of concatenation order in the different traversal methods:

Pre: x :: (preorder tl) @ (preorder tr)

  1. x : current value
  2. preorder tl : visit left tree
  3. preorder tr : visit right tree

In: (inorder tl) @ [x] @ (inorder tr)

  1. inorder tl : visit left tree
  2. x : current value
  3. inorder tr : visit right tree

Post: (postorder tl) @ (postorder tr) @ [x]

  1. postorder tl : visit left tree
  2. postorder tr : visit right tree
  3. x : current value

If you trace around your tree anti-clockwise starting at the top (above the root):

  • Pre-order traversal returns the elements in the order of where you encounter the left-hand side of each node first.
  • In-order traversal returns the elements in the order of where you encounter the bottom of each node first.
  • Post-order traversal returns the elements in the order of where you encounter the right-hand side of each node first.

As a brief overview, pre-order traversal is useful for duplicating entire trees, in-order travel is useful for binary searching and post-order traversal is useful for deletion of entire trees.

More details can be found here: https://en.wikipedia.org/wiki/Tree_traversal

Upvotes: 3

Mikhail Shilkov
Mikhail Shilkov

Reputation: 35134

If you run your own code, you will see the difference in results:

> preorder someTree;;
val it : int list = [20; 40; 2; -2; 0]
> inorder someTree;;
val it : int list = [20; 40; -2; 2; 0]
> postorder someTree;;
val it : int list = [-2; 0; 2; 40; 20]

So, the difference is in order of the list elements.

Upvotes: 0

Related Questions