Task

Implement a binary tree where each node carries an integer,   and implement:

   pre-order,
   in-order, 
   post-order,     and 
   level-order   traversal. 


Use those traversals to output the following tree:

         1
        / \
       /   \
      /     \
     2       3
    / \     /
   4   5   6
  /       / \
 7       8   9

The correct output should look like this:

preorder:    1 2 4 7 5 3 6 8 9
inorder:     7 4 2 5 1 8 6 9 3
postorder:   7 4 5 2 8 9 6 3 1
level-order: 1 2 3 4 5 6 7 8 9



See also

   Wikipedia article:   Tree traversal.


import deques
 
type
  Node[T] = ref object
    data: T
    left, right: Node[T]
 
proc newNode[T](data: T; left, right: Node[T] = nil): Node[T] =
  Node[T](data: data, left: left, right: right)
 
proc preorder[T](n: Node[T]): seq[T] =
  if n.isNil: @[]
  else: @[n.data] & preorder(n.left) & preorder(n.right)
 
proc inorder[T](n: Node[T]): seq[T] =
  if n.isNil: @[]
  else: inorder(n.left) & @[n.data] & inorder(n.right)
 
proc postorder[T](n: Node[T]): seq[T] =
  if n.isNil: @[]
  else: postorder(n.left) & postorder(n.right) & @[n.data]
 
proc levelorder[T](n: Node[T]): seq[T] =
  var queue: Deque[Node[T]]
  queue.addLast(n)
  while queue.len > 0:
    let next = queue.popFirst()
    result.add next.data
    if not next.left.isNil: queue.addLast(next.left)
    if not next.right.isNil: queue.addLast(next.right)
 
let tree = 1.newNode(
             2.newNode(
               4.newNode(
                 7.newNode),
               5.newNode),
             3.newNode(
               6.newNode(
                 8.newNode,
                 9.newNode)))
 
echo preorder tree
echo inorder tree
echo postorder tree
echo levelorder tree