## Go


### Individually allocated nodes

{{trans|C}}
This is like many examples on this page.

```go
package main

import "fmt"

type node struct {
    value       int
    left, right *node
}

func (n *node) iterPreorder(visit func(int)) {
    if n == nil {
        return
    }
    visit(n.value)
    n.left.iterPreorder(visit)
    n.right.iterPreorder(visit)
}

func (n *node) iterInorder(visit func(int)) {
    if n == nil {
        return
    }
    n.left.iterInorder(visit)
    visit(n.value)
    n.right.iterInorder(visit)
}

func (n *node) iterPostorder(visit func(int)) {
    if n == nil {
        return
    }
    n.left.iterPostorder(visit)
    n.right.iterPostorder(visit)
    visit(n.value)
}

func (n *node) iterLevelorder(visit func(int)) {
    if n == nil {
        return
    }
    for queue := []*node{n}; ; {
        n = queue[0]
        visit(n.value)
        copy(queue, queue[1:])
        queue = queue[:len(queue)-1]
        if n.left != nil {
            queue = append(queue, n.left)
        }
        if n.right != nil {
            queue = append(queue, n.right)
        }
        if len(queue) == 0 {
            return
        }
    }
}

func main() {
    tree := &node{1,
        &node{2,
            &node{4,
                &node{7, nil, nil},
                nil},
            &node{5, nil, nil}},
        &node{3,
            &node{6,
                &node{8, nil, nil},
                &node{9, nil, nil}},
            nil}}
    fmt.Print("preorder:    ")
    tree.iterPreorder(visitor)
    fmt.Println()
    fmt.Print("inorder:     ")
    tree.iterInorder(visitor)
    fmt.Println()
    fmt.Print("postorder:   ")
    tree.iterPostorder(visitor)
    fmt.Println()
    fmt.Print("level-order: ")
    tree.iterLevelorder(visitor)
    fmt.Println()
}

func visitor(value int) {
    fmt.Print(value, " ")
}

{{out}}

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

Flat slice

Alternative representation. Like Wikipedia [http://en.wikipedia.org/wiki/Binary_tree#Arrays Binary tree#Arrays]

package main

import "fmt"

// flat, level-order representation.
// for node at index k, left child has index 2k, right child has index 2k+1.
// a value of -1 means the node does not exist.
type tree []int

func main() {
    t := tree{1, 2, 3, 4, 5, 6, -1, 7, -1, -1, -1, 8, 9}
    visitor := func(n int) {
        fmt.Print(n, " ")
    }
    fmt.Print("preorder:    ")
    t.iterPreorder(visitor)
    fmt.Print("\ninorder:     ")
    t.iterInorder(visitor)
    fmt.Print("\npostorder:   ")
    t.iterPostorder(visitor)
    fmt.Print("\nlevel-order: ")
    t.iterLevelorder(visitor)
    fmt.Println()
}

func (t tree) iterPreorder(visit func(int)) {
    var traverse func(int)
    traverse = func(k int) {
        if k >= len(t) || t[k] == -1 {
            return
        }
        visit(t[k])
        traverse(2*k + 1)
        traverse(2*k + 2)
    }
    traverse(0)
}

func (t tree) iterInorder(visit func(int)) {
    var traverse func(int)
    traverse = func(k int) {
        if k >= len(t) || t[k] == -1 {
            return
        }
        traverse(2*k + 1)
        visit(t[k])
        traverse(2*k + 2)
    }
    traverse(0)
}

func (t tree) iterPostorder(visit func(int)) {
    var traverse func(int)
    traverse = func(k int) {
        if k >= len(t) || t[k] == -1 {
            return
        }
        traverse(2*k + 1)
        traverse(2*k + 2)
        visit(t[k])
    }
    traverse(0)
}

func (t tree) iterLevelorder(visit func(int)) {
    for _, n := range t {
        if n != -1 {
            visit(n)
        }
    }
}

Groovy

Uses Groovy '''Node''' and '''NodeBuilder''' classes

def preorder;
preorder = { Node node ->
    ([node] + node.children().collect { preorder(it) }).flatten()
}

def postorder;
postorder = { Node node ->
    (node.children().collect { postorder(it) } + [node]).flatten()
}

def inorder;
inorder = { Node node ->
    def kids = node.children()
    if (kids.empty) [node]
    else if (kids.size() == 1 &&  kids[0].'@right') [node] + inorder(kids[0])
    else inorder(kids[0]) + [node] + (kids.size()>1 ? inorder(kids[1]) : [])
}

def levelorder = { Node node ->
    def nodeList = []
    def level = [node]
    while (!level.empty) {
        nodeList += level
        def nextLevel = level.collect { it.children() }.flatten()
        level = nextLevel
    }
    nodeList
}

class BinaryNodeBuilder extends NodeBuilder {
    protected Object postNodeCompletion(Object parent, Object node) {
        assert node.children().size() < 3
        node
    }
}

Verify that '''BinaryNodeBuilder''' will not allow a node to have more than 2 children

try {
    new BinaryNodeBuilder().'1' {
        a {}
        b {}
        c {}
    }
    println 'not limited to binary tree\r\n'
} catch (org.codehaus.groovy.transform.powerassert.PowerAssertionError e) {
    println 'limited to binary tree\r\n'
}

Test case #1 (from the task definition)

//               1
//           /       \
//       2               3
//     /   \           /
//   4       5       6
//  /               / \
// 7               8   9
def tree1 = new BinaryNodeBuilder().
'1' {
    '2' {
        '4' { '7' {} }
        '5' {}
    }
    '3' {
        '6' { '8' {}; '9' {} }
    }
}

Test case #2 (tests single right child)

//               1
//           /       \
//       2               3
//     /   \           /
//   4       5       6
//    \             / \
//     7           8   9
def tree2 = new BinaryNodeBuilder().
'1' {
    '2' {
        '4' { '7'(right:true) {} }
        '5' {}
    }
    '3' {
        '6' { '8' {}; '9' {} }
    }
}

Run tests:

def test = { tree ->
    println "preorder:    ${preorder(tree).collect{it.name()}}"
    println "preorder:    ${tree.depthFirst().collect{it.name()}}"

    println "postorder:   ${postorder(tree).collect{it.name()}}"

    println "inorder:     ${inorder(tree).collect{it.name()}}"

    println "level-order: ${levelorder(tree).collect{it.name()}}"
    println "level-order: ${tree.breadthFirst().collect{it.name()}}"

    println()
}
test(tree1)
test(tree2)

Output:

limited to binary tree

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

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

Haskell

data Tree a
  = Empty
  | Node { value :: a
         , left :: Tree a
         , right :: Tree a}

preorder, inorder, postorder, levelorder :: Tree a -> [a]
preorder Empty = []
preorder (Node v l r) = v : preorder l ++ preorder r

inorder Empty = []
inorder (Node v l r) = inorder l ++ (v : inorder r)

postorder Empty = []
postorder (Node v l r) = postorder l ++ postorder r ++ [v]

levelorder x = loop [x]
  where
    loop [] = []
    loop (Empty:xs) = loop xs
    loop (Node v l r:xs) = v : loop (xs ++ [l, r])

-- TEST --------------------------------------------------------------
tree :: Tree Int
tree =
  Node
    1
    (Node 2 (Node 4 (Node 7 Empty Empty) Empty) (Node 5 Empty Empty))
    (Node 3 (Node 6 (Node 8 Empty Empty) (Node 9 Empty Empty)) Empty)

asciiTree :: String
asciiTree =
  unlines
    [ "         1"
    , "        / \\"
    , "       /   \\"
    , "      /     \\"
    , "     2       3"
    , "    / \\     /"
    , "   4   5   6"
    , "  /       / \\"
    , " 7       8   9"
    ]

-- OUTPUT --------------------------------------------------------------
main :: IO ()
main = do
  putStrLn asciiTree
  mapM_ putStrLn $
    zipWith
      (\s xs -> justifyLeft 14 ' ' (s ++ ":") ++ unwords (show <$> xs))
      ["preorder", "inorder", "postorder", "level-order"]
      ([preorder, inorder, postorder, levelorder] <*> [tree])
  where
    justifyLeft n c s = take n (s ++ replicate n c)

{{Out}}

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

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

Or, writing the first three traversals in terms of '''foldTree''', and the last as an iteration of bind ('''>>=''') over sub-trees:

{{Trans|Python}}

import Data.Tree (Tree(..))

preorder :: a -> [[a]] -> [a]
preorder x xs = x : concat xs

inorder :: a -> [[a]] -> [a]
inorder x [] = [x]
inorder x (y:xs) = y ++ [x] ++ concat xs

postorder :: a -> [[a]] -> [a]
postorder x xs = concat xs ++ [x]

foldTree :: (a -> [b] -> b) -> Tree a -> b
foldTree f = go
  where
    go (Node x ts) = f x (go <$> ts)

levelOrder :: Tree a -> [a]
levelOrder x =
  takeWhile (not . null) (iterate (concatMap subForest) [x]) >>= fmap rootLabel

-- TEST -------------------------------------------------
tree :: Tree Int
tree =
  Node
    1
    [ Node 2 [Node 4 [Node 7 []], Node 5 []]
    , Node 3 [Node 6 [Node 8 [], Node 9 []]]
    ]

main :: IO ()
main = do
  mapM_ print ([foldTree] <*> [preorder, inorder, postorder] <*> [tree])
  print $ levelOrder tree

[1,2,4,7,5,3,6,8,9]
[7,4,2,5,1,8,6,9,3]
[7,4,5,2,8,9,6,3,1]
[1,2,3,4,5,6,7,8,9]

=={{header|Icon}} and {{header|Unicon}}==

procedure main()
    bTree := [1, [2, [4, [7]], [5]], [3, [6, [8], [9]]]]
    showTree(bTree, preorder|inorder|postorder|levelorder)
end

procedure showTree(tree, f)
    writes(image(f),":\t")
    every writes(" ",f(tree)[1])
    write()
end

procedure preorder(L)
    if \L then suspend L | preorder(L[2|3])
end

procedure inorder(L)
    if \L then suspend inorder(L[2]) | L | inorder(L[3])
end

procedure postorder(L)
    if \L then suspend postorder(L[2|3]) | L
end

procedure levelorder(L)
    if \L then {
        queue := [L]
        while nextnode := get(queue) do {
            every put(queue, \nextnode[2|3])
            suspend nextnode
            }
        }
end

Output:

->bintree
procedure preorder:      1 2 4 7 5 3 6 8 9
procedure inorder:       7 4 2 5 1 8 6 9 3
procedure postorder:     7 4 5 2 8 9 6 3 1
procedure levelorder:    1 2 3 4 5 6 7 8 9
->

J

preorder=: ]S:0
postorder=: ([:; postorder&.>@}.) , >@{.
levelorder=: ;@({::L:1 _~ [: (/: #@>) <S:1@{::)
inorder=: ([:; inorder&.>@(''"_`(1&{)@.(1<#))) , >@{. , [:; inorder&.>@}.@}.

Required example:

N2=: conjunction def '(<m),(<n),<y'
N1=: adverb def '(<m),<y'
L=: adverb def '<m'

tree=: 1 N2 (2 N2 (4 N1 (7 L)) 5 L) 3 N1 6 N2 (8 L) 9 L

This tree is organized in a pre-order fashion

    preorder tree
1 2 4 7 5 3 6 8 9

post-order is not that much different from pre-order, except that the children must extracted before the parent.

    postorder tree
7 4 5 2 8 9 6 3 1

Implementing in-order is more complex because we must sometimes test whether we have any leaves, instead of relying on J's implicit looping over lists

    inorder tree
7 4 2 5 1 8 6 9 3

level-order can be accomplished by constructing a map of the locations of the leaves, sorting these map locations by their non-leaf indices and using the result to extract all leaves from the tree. Elements at the same level with the same parent will have the same sort keys and thus be extracted in preorder fashion, which works just fine.

    levelorder tree
1 2 3 4 5 6 7 8 9

For J novices, here's the tree instance with a few redundant parenthesis:

    tree=: 1 N2 (2 N2 (4 N1 (7 L)) (5 L)) (3 N1 (6 N2 (8 L) (9 L)))

Syntactically, N2 is a binary node expressed as m N2 n y. N1 is a node with a single child, expressed as m N2 y. L is a leaf node, expressed as m L. In all three cases, the parent value (m) for the node appears on the left, and the child tree(s) appear on the right. (And n must be parenthesized if it is not a single word.)

J: Alternate implementation

Of course, there are other ways of representing tree structures in J. One fairly natural approach pairs a list of data with a matching list of parent indices. For example:

example=:1 8 3 4 7 5 9 6 2,: 0 7 0 8 3 8 7 2 0

Here, we have two possible ways of identifying the root node. It can be in a known place in the list (index 0, for this example). But it is also the only node which is its own parent. For this task we'll use the more general (and thus slower) approach which allows us to place the root node anywhere in the sequence.

Next, let's define a few utilities:

depth=: +/@((~: , (~: i.@#@{.)~) {:@,)@({~^:a:)

reorder=:4 :0
  'data parent'=. y
  data1=. x{data
  parent1=. x{data1 i. parent{data
  if. 0=L.y do. data1,:parent1 else. data1;parent1 end.
)

data=:3 :'data[''data parent''=. y'
parent=:3 :'parent[''data parent''=. y'

childinds=: [: <:@(2&{.@-.&> #\) (</. #\)`(]~.)`(a:"0)}~

Here, data extracts the list of data items from the tree and parent extracts the structure from the tree.

depth examines the parent structure and returns the distance of each node from the root.

reorder is like indexing, except that it returns an equivalent tree (with the structural elements updated to maintain the original tree structure). The left argument for reorder should select the entire tree. Selecting partial trees is a more complex problem which needs specifications about how to deal with issues such as dangling roots and multiple roots. (Our abstraction here has no problem ''representing'' trees with multiple roots, but they are not relevant to this task.)

childinds extracts the child pointers which some of these results assume. This implementation assumes we are working with a binary tree (which is an explicit requirement of this task -- the parent node representation is far more general and can represent trees with any number of children at each node, but what would an "inorder" traversal look like with a trinary tree?).

Next, we define our "traversal" routines (actually, we are going a bit overboard here - we really only need to extract the data for this tasks's concept of traversal):

dataorder=: /:@data reorder ]
levelorder=: /:@depth@parent reorder ]

inorder=: inperm@parent reorder ]
inperm=:3 :0
  chil=. childinds y
  node=. {.I.(= i.@#) y
  todo=. i.0 2
  r=. i.0
  whilst. (#todo)+.0<:node do.
    if. 0 <: node do.
      if. 0 <: {.ch=. node{chil do.
        todo=. todo, node,{:ch
        node=. {.ch
      else.
        r=. r, node
        node=. _1 end.
    else.
      r=. r, {.ch=. {: todo
      todo=. }: todo
      node=. {:ch end. end.
  r
)

postorder=: postperm@parent reorder ]
postperm=:3 :0
  chil=. 0,1+childinds y
  todo=. 1+I.(= i.@#) y
  r=. i.0
  whilst. (#todo) do.
    node=. {: todo
    todo=. }: todo
    if. 0 < node do.
      if. #ch=. (node{chil)-.0 do.
        todo=. todo,(-node),|.ch
      else.
        r=. r, <:node end.
    else.
      r=. r, <:|node  end. end.
)

preorder=: preperm@parent reorder ]
preperm=:3 :0
  chil=. childinds y
  todo=. I.(= i.@#) y
  r=. i.0
  whilst. (#todo) do.
    r=. r,node=. {: todo
    todo=. }: todo
    if. #ch=. (node{chil)-._1 do.
      todo=. todo,|.ch end. end.
  r
)

These routines assume that children of a node are arranged so that the lower index appears to the left of the higher index. If instead we wanted to rely on the ordering of their values, we could first use dataorder to enforce the assumption that child indexes are ordered properly.

Example use:

   levelorder dataorder example
1 2 3 4 5 6 7 8 9
0 0 0 1 1 2 3 5 5
   inorder dataorder example
7 4 2 5 1 8 6 9 3
1 2 4 2 4 6 8 6 4
   preorder dataorder example
1 2 4 7 5 3 6 8 9
0 0 1 2 1 0 5 6 6
   postorder dataorder example
7 4 5 2 8 9 6 3 1
1 3 3 8 6 6 7 8 8

(Once again, all we really need for this task is the first row of those results - the part that represents data.)

Java

{{works with|Java|1.5+}}

import java.util.*;

public class TreeTraversal {

        static class Node<T> {
		T value;
		Node<T> left;
		Node<T> right;

		Node(T value) {
			this.value = value;
		}

		void visit() {
			System.out.print(this.value + " ");
		}
	}

	static enum ORDER {
		PREORDER, INORDER, POSTORDER, LEVEL
	}

        static <T> void traverse(Node<T> node, ORDER order) {
		if (node == null) {
			return;
		}
		switch (order) {
		case PREORDER:
			node.visit();
			traverse(node.left, order);
			traverse(node.right, order);
			break;
		case INORDER:
			traverse(node.left, order);
			node.visit();
			traverse(node.right, order);
			break;
		case POSTORDER:
			traverse(node.left, order);
			traverse(node.right, order);
			node.visit();
			break;
		case LEVEL:
			Queue<Node<T>> queue = new LinkedList<>();
			queue.add(node);
			while(!queue.isEmpty()){
				Node<T> next = queue.remove();
				next.visit();
				if(next.left!=null)
					queue.add(next.left);
				if(next.right!=null)
					queue.add(next.right);
			}
		}
	}

	public static void main(String[] args) {

		Node<Integer> one = new Node<Integer>(1);
		Node<Integer> two = new Node<Integer>(2);
		Node<Integer> three = new Node<Integer>(3);
		Node<Integer> four = new Node<Integer>(4);
		Node<Integer> five = new Node<Integer>(5);
		Node<Integer> six = new Node<Integer>(6);
		Node<Integer> seven = new Node<Integer>(7);
		Node<Integer> eight = new Node<Integer>(8);
		Node<Integer> nine = new Node<Integer>(9);

		one.left = two;
		one.right = three;
		two.left = four;
		two.right = five;
		three.left = six;
		four.left = seven;
		six.left = eight;
		six.right = nine;

		traverse(one, ORDER.PREORDER);
		System.out.println();
		traverse(one, ORDER.INORDER);
		System.out.println();
		traverse(one, ORDER.POSTORDER);
		System.out.println();
		traverse(one, ORDER.LEVEL);

	}
}

Output:

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

JavaScript

ES5

=Iteration=

inspired by [[#Ruby|Ruby]]

function BinaryTree(value, left, right) {
    this.value = value;
    this.left = left;
    this.right = right;
}
BinaryTree.prototype.preorder  = function(f) {this.walk(f,['this','left','right'])}
BinaryTree.prototype.inorder   = function(f) {this.walk(f,['left','this','right'])}
BinaryTree.prototype.postorder = function(f) {this.walk(f,['left','right','this'])}
BinaryTree.prototype.walk = function(func, order) {
    for (var i in order)
        switch (order[i]) {
            case "this": func(this.value); break;
            case "left": if (this.left) this.left.walk(func, order); break;
            case "right": if (this.right) this.right.walk(func, order); break;
        }
}
BinaryTree.prototype.levelorder = function(func) {
    var queue = [this];
    while (queue.length != 0) {
        var node = queue.shift();
        func(node.value);
        if (node.left) queue.push(node.left);
        if (node.right) queue.push(node.right);
    }
}

// convenience function for creating a binary tree
function createBinaryTreeFromArray(ary) {
    var left = null, right = null;
    if (ary[1]) left = createBinaryTreeFromArray(ary[1]);
    if (ary[2]) right = createBinaryTreeFromArray(ary[2]);
    return new BinaryTree(ary[0], left, right);
}

var tree = createBinaryTreeFromArray([1, [2, [4, [7]], [5]], [3, [6, [8],[9]]]]);

print("*** preorder ***");   tree.preorder(print);
print("*** inorder ***");    tree.inorder(print);
print("*** postorder ***");  tree.postorder(print);
print("*** levelorder ***"); tree.levelorder(print);

=Functional composition=

{{Trans|Haskell}} (for binary trees consisting of nested lists)

(function () {

    function preorder(n) {
        return [n[v]].concat(
            n[l] ? preorder(n[l]) : []
        ).concat(
            n[r] ? preorder(n[r]) : []
        );
    }

    function inorder(n) {
        return (
            n[l] ? inorder(n[l]) : []
        ).concat(
            n[v]
        ).concat(
            n[r] ? inorder(n[r]) : []
        );
    }

    function postorder(n) {
        return (
            n[l] ? postorder(n[l]) : []
        ).concat(
            n[r] ? postorder(n[r]) : []
        ).concat(
            n[v]
        );
    }

    function levelorder(n) {
        return (function loop(x) {
            return x.length ? (
                x[0] ? (
                [x[0][v]].concat(
                        loop(
                            x.slice(1).concat(
                                [x[0][l], x[0][r]]
                            )
                        )
                    )
                ) : loop(x.slice(1))
            ) : [];
        })([n]);
    }

    var v = 0,
        l = 1,
        r = 2,

        tree = [1,
                [2,
                    [4,
                        [7]
                    ],
                    [5]
                ],
                [3,
                    [6,
                        [8],
                        [9]
                    ]
                ]
            ],

        lstTest = [["Traversal", "Nodes visited"]].concat(
            [preorder, inorder, postorder, levelorder].map(
                function (f) {
                    return [f.name, f(tree)];
                }
            )
        );

    // [[a]] -> bool -> s -> s
    function wikiTable(lstRows, blnHeaderRow, strStyle) {
        return '{| class="wikitable" ' + (
            strStyle ? 'style="' + strStyle + '"' : ''
        ) + lstRows.map(function (lstRow, iRow) {
            var strDelim = ((blnHeaderRow && !iRow) ? '!' : '|');

            return '\n|-\n' + strDelim + ' ' + lstRow.map(function (v) {
                return typeof v === 'undefined' ? ' ' : v;
            }).join(' ' + strDelim + strDelim + ' ');
        }).join('') + '\n|}';
    }

    return wikiTable(lstTest, true) + '\n\n' + JSON.stringify(lstTest);

})();

Output:

{| class="wikitable" |- ! Traversal !! Nodes visited |- | 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 |- | levelorder || 1,2,3,4,5,6,7,8,9 |}

[["Traversal","Nodes visited"],
["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]],["levelorder",[1,2,3,4,5,6,7,8,9]]]

or, again functionally, but:

for a tree of nested dictionaries (rather than a simple nested list),

defining a single '''traverse()''' function

checking that the tree is indeed binary, and returning ''undefined'' for the ''in-order'' traversal if any node in the tree has more than two children. (The other 3 traversals are still defined for rose trees).

(function () {
    'use strict';

    // 'preorder' | 'inorder' | 'postorder' | 'level-order'

    // traverse :: String -> Tree {value: a, nest: [Tree]} -> [a]
    function traverse(strOrderName, dctTree) {
        var strName = strOrderName.toLowerCase();

        if (strName.startsWith('level')) {

            // LEVEL-ORDER
            return levelOrder([dctTree]);

        } else if (strName.startsWith('in')) {
            var lstNest = dctTree.nest;

            if ((lstNest ? lstNest.length : 0) < 3) {
                var left = lstNest[0] || [],
                    right = lstNest[1] || [],

                    lstLeft = left.nest ? (
                        traverse(strName, left)
                    ) : (left.value || []),
                    lstRight = right.nest ? (
                        traverse(strName, right)
                    ) : (right.value || []);

                return (lstLeft !== undefined && lstRight !== undefined) ?

                    // IN-ORDER
                    (lstLeft instanceof Array ? lstLeft : [lstLeft])
                    .concat(dctTree.value)
                    .concat(lstRight) : undefined;

            } else { // in-order only defined here for binary trees
                return undefined;
            }

        } else {
            var lstTraversed = concatMap(function (x) {
                return traverse(strName, x);
            }, (dctTree.nest || []));

            return (
                strName.startsWith('pre') ? (

                    // PRE-ORDER
                    [dctTree.value].concat(lstTraversed)

                ) : strName.startsWith('post') ? (

                    // POST-ORDER
                    lstTraversed.concat(dctTree.value)

                ) : []
            );
        }
    }

    // levelOrder :: [Tree {value: a, nest: [Tree]}] -> [a]
    function levelOrder(lstTree) {
        var lngTree = lstTree.length,
            head = lngTree ? lstTree[0] : undefined,
            tail = lstTree.slice(1);

        // Recursively take any value found in the head node
        // of the remaining tail, deferring any child nodes
        // of that head to the end of the tail
        return lngTree ? (
            head ? (
                [head.value].concat(
                    levelOrder(
                        tail
                        .concat(head.nest || [])
                    )
                )
            ) : levelOrder(tail)
        ) : [];
    }

    // concatMap :: (a -> [b]) -> [a] -> [b]
    function concatMap(f, xs) {
        return [].concat.apply([], xs.map(f));
    }

    var dctTree = {
        value: 1,
        nest: [{
            value: 2,
            nest: [{
                value: 4,
                nest: [{
                    value: 7
                }]
            }, {
                value: 5
            }]
        }, {
            value: 3,
            nest: [{
                value: 6,
                nest: [{
                    value: 8
                }, {
                    value: 9
                }]
            }]
        }]
    };


    return ['preorder', 'inorder', 'postorder', 'level-order']
        .reduce(function (a, k) {
            return (
                a[k] = traverse(k, dctTree),
                a
            );
        }, {});

})();

{{Out}}

{"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]}

ES6

{{Trans|Haskell}}

(() => {
    // TRAVERSALS -------------------------------------------------------------

    // preorder Tree a -> [a]
    const preorder = a => [a[v]]
        .concat(a[l] ? preorder(a[l]) : [])
        .concat(a[r] ? preorder(a[r]) : []);

    // inorder Tree a -> [a]
    const inorder = a =>
        (a[l] ? inorder(a[l]) : [])
        .concat(a[v])
        .concat(a[r] ? inorder(a[r]) : []);

    // postorder Tree a -> [a]
    const postorder = a =>
        (a[l] ? postorder(a[l]) : [])
        .concat(a[r] ? postorder(a[r]) : [])
        .concat(a[v]);

    // levelorder Tree a -> [a]
    const levelorder = a => (function go(x) {
        return x.length ? (
            x[0] ? (
                [x[0][v]].concat(
                    go(x.slice(1)
                        .concat([x[0][l], x[0][r]])
                    )
                )
            ) : go(x.slice(1))
        ) : [];
    })([a]);


    // GENERIC FUNCTIONS  -----------------------------------------------------

    // A list of functions applied to a list of arguments
    // <*> :: [(a -> b)] -> [a] -> [b]
    const ap = (fs, xs) => //
        [].concat.apply([], fs.map(f => //
            [].concat.apply([], xs.map(x => [f(x)]))));

    // intercalate :: String -> [a] -> String
    const intercalate = (s, xs) => xs.join(s);

    // justifyLeft :: Int -> Char -> Text -> Text
    const justifyLeft = (n, cFiller, strText) =>
        n > strText.length ? (
            (strText + cFiller.repeat(n))
            .substr(0, n)
        ) : strText;

    // unlines :: [String] -> String
    const unlines = xs => xs.join('\n');

    // unwords :: [String] -> String
    const unwords = xs => xs.join(' ');

    // zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
    const zipWith = (f, xs, ys) =>
        Array.from({
            length: Math.min(xs.length, ys.length)
        }, (_, i) => f(xs[i], ys[i]));

    // TEST -------------------------------------------------------------------
    // asciiTree :: String
    const asciiTree = unlines([
        '         1',
        '        / \\',
        '       /   \\',
        '      /     \\',
        '     2       3',
        '    / \\     /',
        '   4   5   6',
        '  /       / \\',
        ' 7       8   9'
    ]);

    const [v, l, r] = [0, 1, 2],
    tree = [1, [2, [4, [7]],
                [5]
            ],
            [3, [6, [8],
                [9]
            ]]
        ],

        // fs :: [(Tree a -> [a])]
        fs = [preorder, inorder, postorder, levelorder];

    return asciiTree + '\n\n' +
        intercalate('\n',
            zipWith(
                (f, xs) => justifyLeft(12, ' ', f.name + ':') + unwords(xs),
                fs,
                ap(fs, [tree])
            )
        );
})();

{{Out}}

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

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
levelorder: 1 2 3 4 5 6 7 8 9

jq

All the ordering filters defined here produce streams. For the final output, each stream is condensed into an array.

The implementation assumes an array structured recursively as [ node, left, right ], where "left" and "right" may be [] or null equivalently.

def preorder:
  if length == 0 then empty
  else .[0], (.[1]|preorder), (.[2]|preorder)
  end;

def inorder:
  if length == 0 then empty
  else (.[1]|inorder), .[0] , (.[2]|inorder)
  end;

def postorder:
  if length == 0 then empty
  else (.[1] | postorder), (.[2]|postorder), .[0]
  end;

# Helper functions for levelorder:
  # Produce a stream of the first elements
  def heads: map( .[0] | select(. != null)) | .[];

# Produce a stream of the left/right branches:
  def tails:
    if length == 0 then empty
    else [map ( .[1], .[2] ) | .[] | select( . != null)]
    end;

def levelorder: [.] | recurse( tails ) | heads;

'''The task''':

def task:
  # [node, left, right]
  def atree: [1, [2, [4, [7,[],[]],
                         []],
                     [5, [],[]]],

                 [3, [6, [8,[],[]],
                         [9,[],[]]],
                     []]] ;

  "preorder:   \( [atree|preorder ])",
  "inorder:    \( [atree|inorder  ])",
  "postorder:  \( [atree|postorder ])",
  "levelorder: \( [atree|levelorder])"
;

task

{{Out}} $ jq -n -c -r -f Tree_traversal.jq 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] levelorder: [1,2,3,4,5,6,7,8,9]

Julia

tree = Any[1, Any[2, Any[4, Any[7, Any[],
                                          Any[]],
                                   Any[]],
                            Any[5, Any[],
                                   Any[]]],
                     Any[3, Any[6, Any[8, Any[],
                                          Any[]],
                                   Any[9, Any[],
                                          Any[]]],
                            Any[]]]

preorder(t, f) = if !isempty(t)
                     f(t[1]); preorder(t[2], f); preorder(t[3], f)
                 end

inorder(t, f) = if !isempty(t)
                    inorder(t[2], f); f(t[1]); inorder(t[3], f)
                end

postorder(t, f) = if !isempty(t)
                      postorder(t[2], f); postorder(t[3], f); f(t[1])
                  end

levelorder(t, f) = while !isempty(t)
                       t = mapreduce(x -> isa(x, Number) ? (f(x); []) : x, vcat, t)
                   end

{{Out}}

julia> for f in [preorder, inorder, postorder, levelorder]
           print((lpad("$f: ", 12))); f(tree, x -> print(x, " ")); println()
       end
  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
levelorder: 1 2 3 4 5 6 7 8 9

Kotlin

procedural style

data class Node(val v: Int, var left: Node? = null, var right: Node? = null) {
    override fun toString() = "$v"
}

fun preOrder(n: Node?) {
    n?.let {
        print("$n ")
        preOrder(n.left)
        preOrder(n.right)
    }
}

fun inorder(n: Node?) {
    n?.let {
        inorder(n.left)
        print("$n ")
        inorder(n.right)
    }
}

fun postOrder(n: Node?) {
    n?.let {
        postOrder(n.left)
        postOrder(n.right)
        print("$n ")
    }
}

fun levelOrder(n: Node?) {
    n?.let {
        val queue = mutableListOf(n)
        while (queue.isNotEmpty()) {
            val node = queue.removeAt(0)
            print("$node ")
            node.left?.let { queue.add(it) }
            node.right?.let { queue.add(it) }
        }
    }
}

inline fun exec(name: String, n: Node?, f: (Node?) -> Unit) {
    print(name)
    f(n)
    println()
}

fun main(args: Array<String>) {
    val nodes = Array(10) { Node(it) }

    nodes[1].left = nodes[2]
    nodes[1].right = nodes[3]

    nodes[2].left = nodes[4]
    nodes[2].right = nodes[5]

    nodes[4].left = nodes[7]

    nodes[3].left = nodes[6]

    nodes[6].left = nodes[8]
    nodes[6].right = nodes[9]

    exec("   preOrder: ", nodes[1], ::preOrder)
    exec("    inorder: ", nodes[1], ::inorder)
    exec("  postOrder: ", nodes[1], ::postOrder)
    exec("level-order: ", nodes[1], ::levelOrder)
}

{{Out}}

   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

===object-oriented style===

fun main(args: Array<String>) {
    data class Node(val v: Int, var left: Node? = null, var right: Node? = null) {
        override fun toString() = " $v"

        fun preOrder()  { print(this); left?.preOrder(); right?.preOrder() }
        fun inorder()   { left?.inorder(); print(this); right?.inorder() }
        fun postOrder() { left?.postOrder(); right?.postOrder(); print(this) }

        fun levelOrder() = with(mutableListOf(this)) {
            do {
                val node = removeAt(0)
                print(node)
                node.left?.let { add(it) }
                node.right?.let { add(it) }
            } while (any())
        }

        inline fun exec(name: String, f: (Node) -> Unit) {
            print(name)
            f(this)
            println()
        }
    }

    val nodes = Array(10) { Node(it) }

    nodes[1].left = nodes[2]
    nodes[1].right = nodes[3]
    nodes[2].left = nodes[4]
    nodes[2].right = nodes[5]
    nodes[4].left = nodes[7]
    nodes[3].left = nodes[6]
    nodes[6].left = nodes[8]
    nodes[6].right = nodes[9]

    with(nodes[1]) {
        exec("   preOrder:", Node::preOrder)
        exec("    inorder:", Node::inorder)
        exec("  postOrder:", Node::postOrder)
        exec("level-order:", Node::levelOrder)
    }
}

Lingo

-- parent script "BinaryTreeNode"

property _val, _left, _right

on new (me, val)
  me._val = val
  return me
end

on getValue (me)
  return me._val
end

on setLeft (me, node)
  me._left = node
end

on setRight (me, node)
  me._right = node
end

on getLeft (me)
  return me._left
end

on getRight (me)
  return me._right
end

-- parent script "BinaryTreeTraversal"

on inOrder (me, node, l)
  if voidP(l) then l = []
  if voidP(node) then return l
  if not voidP(node.getLeft()) then l = me.inOrder(node.getLeft(), l)
  l.add(node)
  if not voidP(node.getRight()) then l = me.inOrder(node.getRight(), l)
  return l
end

on preOrder (me, node, l)
  if voidP(l) then l = []
  if voidP(node) then return l
  l.add(node)
  if not voidP(node.getLeft()) then l = me.preOrder(node.getLeft(), l)
  if not voidP(node.getRight()) then l = me.preOrder(node.getRight(), l)
  return l
end

on postOrder (me, node, l)
  if voidP(l) then l = []
  if voidP(node) then return l
  if not voidP(node.getLeft()) then l = me.postOrder(node.getLeft(), l)
  if not voidP(node.getRight()) then l = me.postOrder(node.getRight(), l)
  l.add(node)
  return l
end

on levelOrder (me, node)
  l = []
  queue = [node]
  repeat while queue.count
    node = queue[1]
    queue.deleteAt(1)
    l.add(node)
    if not voidP(node.getLeft()) then queue.add(node.getLeft())
    if not voidP(node.getRight()) then queue.add(node.getRight())
  end repeat
  return l
end

-- print utility function
on serialize (me, l)
  str = ""
  repeat with node in l
    put node.getValue()&" " after str
  end repeat
  delete the last char of str
  return str
end

Usage:

-- create the tree
l = []
repeat with i = 1 to 10
  l[i] = script("BinaryTreeNode").new(i)
end repeat
l[6].setLeft (l[8])
l[6].setRight(l[9])
l[3].setLeft (l[6])
l[4].setLeft (l[7])
l[2].setLeft (l[4])
l[2].setRight(l[5])
l[1].setLeft (l[2])
l[1].setRight(l[3])

-- print traversal results
trav = script("BinaryTreeTraversal")
put "preorder:    " & trav.serialize(trav.preOrder(l[1]))
put "inorder:     " & trav.serialize(trav.inOrder(l[1]))
put "postorder:   " & trav.serialize(trav.postOrder(l[1]))
put "level-order: " & trav.serialize(trav.levelOrder(l[1]))

{{Out}}

-- "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"

Logo

; nodes are [data left right], use "first" to get data

to node.left :node
  if empty? butfirst :node [output []]
  output first butfirst :node
end
to node.right :node
  if empty? butfirst :node [output []]
  if empty? butfirst butfirst :node [output []]
  output first butfirst butfirst :node
end
to max :a :b
  output ifelse :a > :b [:a] [:b]
end
to tree.depth :tree
  if empty? :tree [output 0]
  output 1 + max tree.depth node.left :tree  tree.depth node.right :tree
end

to pre.order :tree :action
  if empty? :tree [stop]
  invoke :action first :tree
  pre.order node.left :tree :action
  pre.order node.right :tree :action
end
to in.order :tree :action
  if empty? :tree [stop]
  in.order node.left :tree :action
  invoke :action first :tree
  in.order node.right :tree :action
end
to post.order :tree :action
  if empty? :tree [stop]
  post.order node.left :tree :action
  post.order node.right :tree :action
  invoke :action first :tree
end
to at.depth :n :tree :action
  if empty? :tree [stop]
  ifelse :n = 1 [invoke :action first :tree] [
    at.depth :n-1 node.left  :tree :action
    at.depth :n-1 node.right :tree :action
  ]
end
to level.order :tree :action
  for [i 1 [tree.depth :tree]] [at.depth :i :tree :action]
end

make "tree [1 [2 [4 [7]]
                 [5]]
              [3 [6 [8]
                    [9]]]]

  pre.order :tree [(type ? "| |)]  (print)
   in.order :tree [(type ? "| |)]  (print)
 post.order :tree [(type ? "| |)]  (print)
level.order :tree [(type ? "| |)]  (print)

Logtalk

:- object(tree_traversal).

    :- public(orders/1).
    orders(Tree) :-
        write('Pre-order:   '), pre_order(Tree), nl,
        write('In-order:    '), in_order(Tree), nl,
        write('Post-order:  '), post_order(Tree), nl,
        write('Level-order: '), level_order(Tree).

    :- public(orders/0).
    orders :-
        tree(Tree),
        orders(Tree).

    tree(
        t(1,
            t(2,
                t(4,
                    t(7, t, t),
                    t
                ),
                t(5, t, t)
            ),
            t(3,
                t(6,
                    t(8, t, t),
                    t(9, t, t)
                ),
                t
            )
        )
    ).

    pre_order(t).
    pre_order(t(Value, Left, Right)) :-
        write(Value), write(' '),
        pre_order(Left),
        pre_order(Right).

    in_order(t).
    in_order(t(Value, Left, Right)) :-
        in_order(Left),
        write(Value), write(' '),
        in_order(Right).

    post_order(t).
    post_order(t(Value, Left, Right)) :-
        post_order(Left),
        post_order(Right),
        write(Value), write(' ').

    level_order(t).
    level_order(t(Value, Left, Right)) :-
        % write tree root value
        write(Value), write(' '),
        % write rest of the tree
        level_order([Left, Right], Tail-Tail).

    level_order([], Trees-[]) :-
        (   Trees \= [] ->
            % print next level
            level_order(Trees, Tail-Tail)
        ;   % no more levels
            true
        ).
    level_order([Tree| Trees], Rest0) :-
        (   Tree = t(Value, Left, Right) ->
            write(Value), write(' '),
            % collect the subtrees to print the next level
            append(Rest0, [Left, Right| Tail]-Tail, Rest1),
            % continue printing the current level
            level_order(Trees, Rest1)
        ;   % continue printing the current level
            level_order(Trees, Rest0)
        ).

    % use difference-lists for constant time append
    append(List1-Tail1, Tail1-Tail2, List1-Tail2).

:- end_object.

Sample output:

| ?- ?- tree_traversal::orders.
Pre-order:   1 2 4 7 5 3 6 8 9
In-order:    7 4 2 5 1 8 6 9 3
Post-order:  7 4 5 2 8 9 6 3 1
Level-order: 1 2 3 4 5 6 7 8 9
yes

Lua

-- Utility
local function append(t1, t2)
    for _, v in ipairs(t2) do
        table.insert(t1, v)
    end
end

-- Node class
local Node = {}
Node.__index = Node

function Node:order(order)
    local r = {}
    append(r, type(self[order[1]]) == "table" and self[order[1]]:order(order) or {self[order[1]]})
    append(r, type(self[order[2]]) == "table" and self[order[2]]:order(order) or {self[order[2]]})
    append(r, type(self[order[3]]) == "table" and self[order[3]]:order(order) or {self[order[3]]})
    return r
end

function Node:levelorder()
    local levelorder = {}
    local queue = {self}
    while next(queue) do
        local node = table.remove(queue, 1)
        table.insert(levelorder, node[1])
        table.insert(queue, node[2])
        table.insert(queue, node[3])
    end
    return levelorder
end

-- Node creator
local function new(value, left, right)
    return value and setmetatable({
        value,
        (type(left) == "table") and new(unpack(left)) or new(left),
        (type(right) == "table") and new(unpack(right)) or new(right),
        }, Node) or nil
end

-- Example
local tree = new(1, {2, {4, 7}, 5}, {3, {6, 8, 9}})
print("preorder:    " .. table.concat(tree:order({1, 2, 3}), " "))
print("inorder:     " .. table.concat(tree:order({2, 1, 3}), " "))
print("postorder:   " .. table.concat(tree:order({2, 3, 1}), " "))
print("level-order: " .. table.concat(tree:levelorder(), " "))

M2000 Interpreter

Using Tuple as Tree

A tuple is an "auto array" in M2000 Interpreter. (,) is the zero length array.

Module CheckIt {
      Null=(,)
      Tree=((((Null,7,Null),4,Null),2,(Null,5,Null)),1,(((Null,8,Null),6,(Null,9,Null)),3,Null))

      Module preorder (T) {
            Print "preorder:    ";
            printtree(T)
            Print
            sub printtree(T)
                  Print T#val(1);" ";
                  If len(T#val(0))>0 then printtree(T#val(0))
                  If len(T#val(2))>0 then printtree(T#val(2))
            end sub
      }
      preorder Tree

      Module inorder (T) {
            Print "inorder:     ";
            printtree(T)
            Print
            sub printtree(T)
                  If len(T#val(0))>0 then printtree(T#val(0))
                  Print T#val(1);" ";
                  If len(T#val(2))>0 then printtree(T#val(2))
            end sub
      }
      inorder Tree

      Module postorder (T) {
            Print "postorder:   ";
            printtree(T)
            Print
            sub printtree(T)
                  If len(T#val(0))>0 then printtree(T#val(0))
                  If len(T#val(2))>0 then printtree(T#val(2))
                  Print T#val(1);" ";
            end sub
      }
      postorder Tree

      Module level_order (T) {
            Print "level-order: ";
            Stack New {
                  printtree(T)
                  if empty then exit
                  Read T
                  Loop
            }
            Print
            sub printtree(T)
                  If Len(T)>0 then
                        Print T#val(1);" ";
                        Data T#val(0), T#val(2)
                  end if
            end sub
      }
      level_order Tree
}
CheckIt

Using OOP

Now tree is nodes with pointers to nodes (a node ifs a Group, the user object) The "as pointer" is optional, but we can use type check if we want.

Module OOP {
      \\ Class is a global function (until this module end)
      Class Null {
      }
      \\ Null is a pointer to an object returned from class Null()
      Global Null->Null()
      Class Node {
      Public:
            x, Group LeftNode, Group RightNode
      Class:
            \\ after class:  anything exist one time,
            \\ not included in final object
            Module Node {
                  .LeftNode<=Null
                  .RightNode<=Null
                  Read .x
                  \\ read ? for optional values
                  Read ? .LeftNode, .RightNode
            }
      }
      \\ NodeTree return a pointer to a new Node
      Function NodeTree {
            \\ ![] pass currrent stack to Node()
            ->Node(![])
      }

      Tree=NodeTree(1, NodeTree(2,NodeTree(4, NodeTree(7)), NodeTree(5)), NodeTree(3, NodeTree(6, NodeTree(8), NodeTree(9))))

      Module preorder (T) {
            Print "preorder:    ";
            printtree(T)
            Print
            sub printtree(T as pointer)
                  If T is Null then Exit sub
                  Print T=>x;" ";
                  printtree(T=>LeftNode)
                  printtree(T=>RightNode)
            end sub
      }
      preorder Tree
      Module inorder (T) {
            Print "inorder:     ";
            printtree(T)
            Print
            sub printtree(T as pointer)
                  If T is Null then Exit sub
                  printtree(T=>LeftNode)
                  Print T=>x;" ";
                  printtree(T=>RightNode)
            end sub
      }
      inorder Tree
      Module postorder (T) {
            Print "postorder:   ";
            printtree(T)
            Print
            sub printtree(T as pointer)
                  If T is Null then Exit sub
                  printtree(T=>LeftNode)
                  printtree(T=>RightNode)
                  Print T=>x;" ";
            end sub
      }
      postorder Tree
      Module level_order (T) {
            Print "level-order: ";
            Stack New {
                  printtree(T)
                  if empty then exit
                  Read T
                  Loop
            }
            Print
            sub printtree(T as pointer)
                  If T is Null else
                        Print T=>x;" ";
                        Data T=>LeftNode, T=>RightNode
                  end if
            end sub
      }
      level_order Tree
}
OOP

or we can put modules inside Node Class as methods also i put a visitor as a call back (a lambda function called as module)

Module OOP {
      \\ Class is a global function (until this module end)
      Class Null {
      }
      \\ Null is a pointer to an object returned from class Null()
      Global Null->Null()
      Class Node {
      Public:
            x, Group LeftNode, Group RightNode
            Module preorder (visitor){
                  T->This
                  printtree(T)
                  sub printtree(T as pointer)
                        If T is Null then Exit sub
                        call visitor(T=>x)
                        printtree(T=>LeftNode)
                        printtree(T=>RightNode)
                  end sub
            }
            Module inorder (visitor){
                  T->This
                  printtree(T)
                  sub printtree(T as pointer)
                        If T is Null then Exit sub
                        printtree(T=>LeftNode)
                        call visitor(T=>x)
                        printtree(T=>RightNode)
                  end sub
            }
            Module postorder (visitor) {
                  T->This
                  printtree(T)
                  sub printtree(T as pointer)
                        If T is Null then Exit sub
                        printtree(T=>LeftNode)
                        printtree(T=>RightNode)
                        call visitor(T=>x)
                  end sub
            }
            Module level_order (visitor){
                  T->This
                  Stack New {
                        printtree(T)
                        if empty then exit
                        Read T
                        Loop
                  }
                  sub printtree(T as pointer)
                        If T is Null else
                              call visitor(T=>x)
                              Data T=>LeftNode, T=>RightNode
                        end if
                  end sub
            }
      Class:
            \\ after class:  anything exist one time,
            \\ not included in final object
            Module Node {
                  .LeftNode<=Null
                  .RightNode<=Null
                  Read .x
                  \\ read ? for optional values
                  Read ? .LeftNode, .RightNode
            }
      }
      \\ NodeTree return a pointer to a new Node
      Function NodeTree {
            \\ ![] pass currrent stack to Node()
            ->Node(![])
      }

      Tree=NodeTree(1, NodeTree(2,NodeTree(4, NodeTree(7)), NodeTree(5)), NodeTree(3, NodeTree(6, NodeTree(8), NodeTree(9))))

      printnum=lambda (title$) -> {
            Print
            Print title$;
            =lambda (x)-> {
                  Print x;" ";
            }
      }
      Tree=>preorder printnum("preorder:    ")
      Tree=>inorder printnum("inorder:     ")
      Tree=>postorder printnum("postorder:   ")
      Tree=>level_order printnum("level-order: ")
}
OOP

Using Event object as visitor

Module OOP {
      \\ Class is a global function (until this module end)
      Class Null {
      }
      \\ Null is a pointer to an object returned from class Null()
      Global Null->Null()
      Class Node {
      Public:
            x, Group LeftNode, Group RightNode
            Module preorder (visitor){
                  T->This
                  printtree(T)
                  sub printtree(T as pointer)
                        If T is Null then Exit sub
                        call event visitor, T=>x
                        printtree(T=>LeftNode)
                        printtree(T=>RightNode)
                  end sub
            }
            Module inorder (visitor){
                  T->This
                  printtree(T)
                  sub printtree(T as pointer)
                        If T is Null then Exit sub
                        printtree(T=>LeftNode)
                        call event visitor, T=>x
                        printtree(T=>RightNode)
                  end sub
            }
            Module postorder (visitor) {
                  T->This
                  printtree(T)
                  sub printtree(T as pointer)
                        If T is Null then Exit sub
                        printtree(T=>LeftNode)
                        printtree(T=>RightNode)
                        call event visitor, T=>x
                  end sub
            }
            Module level_order (visitor){
                  T->This
                  Stack New {
                        printtree(T)
                        if empty then exit
                        Read T
                        Loop
                  }
                  sub printtree(T as pointer)
                        If T is Null else
                              call event visitor, T=>x
                              Data T=>LeftNode, T=>RightNode
                        end if
                  end sub
            }
      Class:
            \\ after class:  anything exist one time,
            \\ not included in final object
            Module Node {
                  .LeftNode<=Null
                  .RightNode<=Null
                  Read .x
                  \\ read ? for optional values
                  Read ? .LeftNode, .RightNode
            }
      }
      \\ NodeTree return a pointer to a new Node
      Function NodeTree {
            \\ ![] pass currrent stack to Node()
            ->Node(![])
      }

      Tree=NodeTree(1, NodeTree(2,NodeTree(4, NodeTree(7)), NodeTree(5)), NodeTree(3, NodeTree(6, NodeTree(8), NodeTree(9))))
      Event PrintAnum {
            read x
      }
      Function PrintThis(x) {
                Print x;" ";
      }
      Event PrintAnum New PrintThis()
      printnum=lambda PrintAnum (title$) -> {
            Print
            Print title$;
            =PrintAnum
      }
      Tree=>preorder printnum("preorder:    ")
      Tree=>inorder printnum("inorder:     ")
      Tree=>postorder printnum("postorder:   ")
      Tree=>level_order printnum("level-order: ")
}
OOP

{{out}}

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
</pre >


## Mathematica


```mathematica
preorder[a_Integer] := a;
preorder[a_[b__]] := Flatten@{a, preorder /@ {b}};
inorder[a_Integer] := a;
inorder[a_[b_, c_]] := Flatten@{inorder@b, a, inorder@c};
inorder[a_[b_]] := Flatten@{inorder@b, a}; postorder[a_Integer] := a;
postorder[a_[b__]] := Flatten@{postorder /@ {b}, a};
levelorder[a_] :=
 Flatten[Table[Level[a, {n}], {n, 0, Depth@a}]] /. {b_Integer[__] :>
    b};

Example:

preorder[1[2[4[7], 5], 3[6[8, 9]]]]
inorder[1[2[4[7], 5], 3[6[8, 9]]]]
postorder[1[2[4[7], 5], 3[6[8, 9]]]]
levelorder[1[2[4[7], 5], 3[6[8, 9]]]]

Output:

{1, 2, 4, 7, 5, 3, 6, 8, 9}

{7, 4, 2, 5, 1, 8, 6, 9, 3}

{7, 4, 5, 2, 8, 9, 6, 3, 1}

{1, 2, 3, 4, 5, 6, 7, 8, 9}

Mercury

:- module tree_traversal.
:- interface.

:- import_module io.

:- pred main(io::di, io::uo) is det.

:- implementation.

:- import_module list.

:- type tree(V)
    --->    empty
    ;       node(V, tree(V), tree(V)).

:- pred preorder(pred(V, A, A), tree(V), A, A).
:- mode preorder(pred(in, di, uo) is det, in, di, uo) is det.

preorder(_, empty, !Acc).
preorder(P, node(Value, Left, Right), !Acc) :-
    P(Value, !Acc),
    preorder(P, Left, !Acc),
    preorder(P, Right, !Acc).

:- pred inorder(pred(V, A, A), tree(V), A, A).
:- mode inorder(pred(in, di, uo) is det, in, di, uo) is det.

inorder(_, empty, !Acc).
inorder(P, node(Value, Left, Right), !Acc) :-
    inorder(P, Left, !Acc),
    P(Value, !Acc),
    inorder(P, Right, !Acc).

:- pred postorder(pred(V, A, A), tree(V), A, A).
:- mode postorder(pred(in, di, uo) is det, in, di, uo) is det.

postorder(_, empty, !Acc).
postorder(P, node(Value, Left, Right), !Acc) :-
    postorder(P, Left, !Acc),
    postorder(P, Right, !Acc),
    P(Value, !Acc).

:- pred levelorder(pred(V, A, A), tree(V), A, A).
:- mode levelorder(pred(in, di, uo) is det, in, di, uo) is det.

levelorder(P, Tree, !Acc) :-
    do_levelorder(P, [Tree], !Acc).

:- pred do_levelorder(pred(V, A, A), list(tree(V)), A, A).
:- mode do_levelorder(pred(in, di, uo) is det, in, di, uo) is det.

do_levelorder(_, [], !Acc).
do_levelorder(P, [empty | Xs], !Acc) :-
   do_levelorder(P, Xs, !Acc).
do_levelorder(P, [node(Value, Left, Right) | Xs], !Acc) :-
   P(Value, !Acc),
   do_levelorder(P, Xs ++ [Left, Right], !Acc).

:- func tree = tree(int).

tree =
    node(1,
        node(2,
            node(4,
                node(7, empty, empty),
                empty
            ),
            node(5, empty, empty)
        ),
        node(3,
            node(6,
                node(8, empty, empty),
                node(9, empty, empty)
            ),
            empty
        )
    ).

main(!IO) :-
     io.write_string("preorder:   " ,!IO),
     preorder(print_value, tree, !IO), io.nl(!IO),
     io.write_string("inorder:    " ,!IO),
     inorder(print_value, tree, !IO), io.nl(!IO),
     io.write_string("postorder:  " ,!IO),
     postorder(print_value, tree, !IO), io.nl(!IO),
     io.write_string("levelorder: " ,!IO),
     levelorder(print_value, tree, !IO), io.nl(!IO).

:- pred print_value(V::in, io::di, io::uo) is det.

print_value(V, !IO) :-
    io.print(V, !IO),
    io.write_string(" ", !IO).

Output:

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
levelorder: 1 2 3 4 5 6 7 8 9

Nim

import queues, sequtils

type
  Node[T] = ref TNode[T]
  TNode[T] = 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 == nil: @[]
  else: @[n.data] & preorder(n.left) & preorder(n.right)

proc inorder[T](n: Node[T]): seq[T] =
  if n == nil: @[]
  else: inorder(n.left) & @[n.data] & inorder(n.right)

proc postorder[T](n: Node[T]): seq[T] =
  if n == nil: @[]
  else: postorder(n.left) & postorder(n.right) & @[n.data]

proc levelorder[T](n: Node[T]): seq[T] =
  result = @[]
  var queue = initQueue[Node[T]]()
  queue.enqueue(n)
  while queue.len > 0:
    let next = queue.dequeue()
    result.add next.data
    if next.left != nil: queue.enqueue(next.left)
    if next.right != nil: queue.enqueue(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

Output:

@[1, 2, 4, 7, 5, 3, 6, 8, 9]
@[7, 4, 2, 5, 1, 8, 6, 9, 3]
@[7, 4, 5, 2, 8, 9, 6, 3, 1]
@[1, 2, 3, 4, 5, 6, 7, 8, 9]

Objeck

use Collection;

class Test {
  function : Main(args : String[]) ~ Nil {
    one := Node->New(1);
    two := Node->New(2);
    three := Node->New(3);
    four := Node->New(4);
    five := Node->New(5);
    six := Node->New(6);
    seven := Node->New(7);
    eight := Node->New(8);
    nine := Node->New(9);

    one->SetLeft(two); one->SetRight(three);
    two->SetLeft(four); two->SetRight(five);
    three->SetLeft(six); four->SetLeft(seven);
    six->SetLeft(eight); six->SetRight(nine);

    "Preorder: "->Print(); Preorder(one);
    "\nInorder: "->Print(); Inorder(one);
    "\nPostorder: "->Print(); Postorder(one);
    "\nLevelorder: "->Print(); Levelorder(one);
    "\n"->Print();
  }

  function : Preorder(node : Node) ~ Nil {
    if(node <> Nil) {
      System.IO.Console->Print(node->GetData())->Print(", ");
      Preorder(node->GetLeft());
      Preorder(node->GetRight());
    };
  }

  function : Inorder(node : Node) ~ Nil {
    if(node <> Nil) {
      Inorder(node->GetLeft());
      System.IO.Console->Print(node->GetData())->Print(", ");
      Inorder(node->GetRight());
    };
  }

  function : Postorder(node : Node) ~ Nil {
    if(node <> Nil) {
      Postorder(node->GetLeft());
      Postorder(node->GetRight());
      System.IO.Console->Print(node->GetData())->Print(", ");
    };
  }

  function : Levelorder(node : Node) ~ Nil {
    nodequeue := Collection.Queue->New();
    if(node <> Nil) {
      nodequeue->Add(node);
    };

    while(nodequeue->IsEmpty() = false) {
      next := nodequeue->Remove()->As(Node);
      System.IO.Console->Print(next->GetData())->Print(", ");
      if(next->GetLeft() <> Nil) {
        nodequeue->Add(next->GetLeft());
      };

      if(next->GetRight() <> Nil) {
        nodequeue->Add(next->GetRight());
      };
    };
  }
}

class Node from BasicCompare {
  @left : Node;
  @right : Node;
  @data : Int;

  New(data : Int) {
    Parent();
    @data := data;
  }

  method : public : GetData() ~ Int {
    return @data;
  }

  method : public : SetLeft(left : Node) ~ Nil {
    @left := left;
  }

  method : public : GetLeft() ~ Node {
    return @left;
  }

  method : public : SetRight(right : Node) ~ Nil {
    @right := right;
  }

  method : public : GetRight() ~ Node {
    return @right;
  }

  method : public : Compare(rhs : Compare) ~ Int {
    right : Node := rhs->As(Node);
    if(@data = right->GetData()) {
      return 0;
    }
    else if(@data < right->GetData()) {
      return -1;
    };

    return 1;
  }
}

Output:

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,
Levelorder: 1, 2, 3, 4, 5, 6, 7, 8, 9,

OCaml

type 'a tree = Empty
             | Node of 'a * 'a tree * 'a tree

let rec preorder f = function
    Empty        -> ()
  | Node (v,l,r) -> f v;
                    preorder f l;
                    preorder f r

let rec inorder f = function
    Empty        -> ()
  | Node (v,l,r) -> inorder f l;
                    f v;
                    inorder f r

let rec postorder f = function
    Empty        -> ()
  | Node (v,l,r) -> postorder f l;
                    postorder f r;
                    f v

let levelorder f x =
  let queue = Queue.create () in
    Queue.add x queue;
    while not (Queue.is_empty queue) do
      match Queue.take queue with
          Empty        -> ()
        | Node (v,l,r) -> f v;
                          Queue.add l queue;
                          Queue.add r queue
    done

let tree =
  Node (1,
        Node (2,
              Node (4,
                    Node (7, Empty, Empty),
                    Empty),
              Node (5, Empty, Empty)),
        Node (3,
              Node (6,
                    Node (8, Empty, Empty),
                    Node (9, Empty, Empty)),
              Empty))

let () =
  preorder   (Printf.printf "%d ") tree; print_newline ();
  inorder    (Printf.printf "%d ") tree; print_newline ();
  postorder  (Printf.printf "%d ") tree; print_newline ();
  levelorder (Printf.printf "%d ") tree; print_newline ()

Output:

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

Oforth

Object Class new: Tree(v, l, r)

Tree method: initialize(v, l, r)  v := v l := l r := r ;
Tree method: v   @v ;
Tree method: l   @l ;
Tree method: r   @r ;

Tree method: preOrder(f)
   @v f perform
   @l ifNotNull: [ @l preOrder(f) ]
   @r ifNotNull: [ @r preOrder(f) ] ;

Tree method: inOrder(f)
   @l ifNotNull: [ @l inOrder(f) ]
   @v f perform
   @r ifNotNull: [ @r inOrder(f) ] ;

Tree method: postOrder(f)
   @l ifNotNull: [ @l postOrder(f) ]
   @r ifNotNull: [ @r postOrder(f) ]
   @v f perform ;

Tree method: levelOrder(f)
| c n |
   Channel new self over send drop ->c
   while(c notEmpty) [
      c receive ->n
      n v f perform
      n l dup ifNotNull: [ c send ] drop
      n r dup ifNotNull: [ c send ] drop
      ] ;

{{out}}

>Tree new(3, Tree new(6, Tree new(8, null, null), Tree new(9, null, null)), null)
ok
>Tree new(2, Tree new(4, Tree new(7, null, null), null), Tree new(5, null, null))
ok
>1 Tree new
ok
>
ok
>dup preOrder(#.)
1 2 4 7 5 3 6 8 9 ok
>dup inOrder(#.)
7 4 2 5 1 8 6 9 3 ok
>dup postOrder(#.)
7 4 5 2 8 9 6 3 1 ok
>dup levelOrder(#.)
1 2 3 4 5 6 7 8 9 ok

ooRexx

  one = .Node~new(1);
  two = .Node~new(2);
  three = .Node~new(3);
  four = .Node~new(4);
  five = .Node~new(5);
  six = .Node~new(6);
  seven = .Node~new(7);
  eight = .Node~new(8);
  nine = .Node~new(9);

  one~left = two
  one~right = three
  two~left = four
  two~right = five
  three~left = six
  four~left = seven
  six~left = eight
  six~right = nine

  out = .array~new
  .treetraverser~preorder(one, out);
  say "Preorder:  " out~toString("l", ", ")
  out~empty
  .treetraverser~inorder(one, out);
  say "Inorder:   " out~toString("l", ", ")
  out~empty
  .treetraverser~postorder(one, out);
  say "Postorder: " out~toString("l", ", ")
  out~empty
  .treetraverser~levelorder(one, out);
  say "Levelorder:" out~toString("l", ", ")


::class node
::method init
  expose left right data
  use strict arg data
  left = .nil
  right = .nil

::attribute left
::attribute right
::attribute data

::class treeTraverser
::method preorder class
  use arg node, out
  if node \== .nil then do
      out~append(node~data)
      self~preorder(node~left, out)
      self~preorder(node~right, out)
  end

::method inorder class
  use arg node, out
  if node \== .nil then do
      self~inorder(node~left, out)
      out~append(node~data)
      self~inorder(node~right, out)
  end

::method postorder class
  use arg node, out
  if node \== .nil then do
      self~postorder(node~left, out)
      self~postorder(node~right, out)
      out~append(node~data)
  end

::method levelorder class
  use arg node, out

  if node == .nil then return
  nodequeue = .queue~new
  nodequeue~queue(node)
  loop while \nodequeue~isEmpty
      next = nodequeue~pull
      out~append(next~data)
      if next~left \= .nil then
          nodequeue~queue(next~left)
      if next~right \= .nil then
          nodequeue~queue(next~right)
  end

Output:

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
Levelorder: 1, 2, 3, 4, 5, 6, 7, 8, 9

Oz

declare
  Tree = n(1
           n(2
             n(4 n(7 e e) e)
             n(5 e e))
           n(3
             n(6 n(8 e e) n(9 e e))
             e))

  fun {Concat Xs}
     {FoldR Xs Append nil}
  end

  fun {Preorder T}
     case T of e then nil
     [] n(V L R) then
        {Concat [[V]
                 {Preorder L}
                 {Preorder R}]}
     end
  end

  fun {Inorder T}
     case T of e then nil
     [] n(V L R) then
        {Concat [{Inorder L}
                 [V]
                 {Inorder R}]}
     end
  end

  fun {Postorder T}
     case T of e then nil
     [] n(V L R) then
        {Concat [{Postorder L}
                 {Postorder R}
                 [V]]}
     end
  end

  local
     fun {Collect Queue}
        case Queue of nil then nil
        [] e|Xr then {Collect Xr}
        [] n(V L R)|Xr then
           V|{Collect {Append Xr [L R]}}
        end
     end
  in
     fun {Levelorder T}
        {Collect [T]}
     end
  end
in
  {Show {Preorder Tree}}
  {Show {Inorder Tree}}
  {Show {Postorder Tree}}
  {Show {Levelorder Tree}}

Perl

Tree nodes are represented by 3-element arrays: [0] - the value; [1] - left child; [2] - right child.

sub preorder
{
	my $t = shift or return ();
	return ($t->[0], preorder($t->[1]), preorder($t->[2]));
}

sub inorder
{
	my $t = shift or return ();
	return (inorder($t->[1]), $t->[0], inorder($t->[2]));
}

sub postorder
{
	my $t = shift or return ();
	return (postorder($t->[1]), postorder($t->[2]), $t->[0]);
}

sub depth
{
	my @ret;
	my @a = ($_[0]);
	while (@a) {
		my $v = shift @a or next;
		push @ret, $v->[0];
		push @a, @{$v}[1,2];
	}
	return @ret;
}

my $x = [1,[2,[4,[7]],[5]],[3,[6,[8],[9]]]];

print "pre:   @{[preorder($x)]}\n";
print "in:    @{[inorder($x)]}\n";
print "post:  @{[postorder($x)]}\n";
print "depth: @{[depth($x)]}\n";

Output:

pre:   1 2 4 7 5 3 6 8 9
in:    7 4 2 5 1 8 6 9 3
post:  7 4 5 2 8 9 6 3 1
depth: 1 2 3 4 5 6 7 8 9

Perl 6

class TreeNode {
    has TreeNode $.parent;
    has TreeNode $.left;
    has TreeNode $.right;
    has $.value;

    method pre-order {
        flat gather {
            take $.value;
            take $.left.pre-order if $.left;
            take $.right.pre-order if $.right
        }
    }

    method in-order {
        flat gather {
            take $.left.in-order if $.left;
            take $.value;
            take $.right.in-order if $.right;
        }
    }

    method post-order {
        flat gather {
            take $.left.post-order if $.left;
            take $.right.post-order if $.right;
            take $.value;
        }
    }

    method level-order {
        my TreeNode @queue = (self);
        flat gather while @queue.elems {
            my $n = @queue.shift;
            take $n.value;
            @queue.push($n.left) if $n.left;
            @queue.push($n.right) if $n.right;
        }
    }
}

my TreeNode $root .= new( value => 1,
                    left => TreeNode.new( value => 2,
                            left => TreeNode.new( value => 4, left => TreeNode.new(value => 7)),
                            right => TreeNode.new( value => 5)
                    ),
                    right => TreeNode.new( value => 3,
                             left => TreeNode.new( value => 6,
                                     left => TreeNode.new(value => 8),
                                     right => TreeNode.new(value => 9)
                                     )
                             )
                    );

say "preorder:  ",$root.pre-order.join(" ");
say "inorder:   ",$root.in-order.join(" ");
say "postorder: ",$root.post-order.join(" ");
say "levelorder:",$root.level-order.join(" ");

{{out}}

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
levelorder:1 2 3 4 5 6 7 8 9

Phix

Copy of [[Tree_traversal#Euphoria|Euphoria]]. This is included in the distribution as demo\rosetta\Tree_traversal.exw, which also contains a way to build such a nested structure, and thirdly a "flat list of nodes" tree, that allows more interesting options such as a tag sort.

constant VALUE = 1, LEFT = 2, RIGHT = 3

constant tree = {1, {2, {4, {7, 0, 0}, 0},
                        {5, 0, 0}},
                    {3, {6, {8, 0, 0},
                            {9, 0, 0}},
                        0}}

procedure preorder(object tree)
    if sequence(tree) then
        printf(1,"%d ",{tree[VALUE]})
        preorder(tree[LEFT])
        preorder(tree[RIGHT])
    end if
end procedure

procedure inorder(object tree)
    if sequence(tree) then
        inorder(tree[LEFT])
        printf(1,"%d ",{tree[VALUE]})
        inorder(tree[RIGHT])
    end if
end procedure

procedure postorder(object tree)
    if sequence(tree) then
        postorder(tree[LEFT])
        postorder(tree[RIGHT])
        printf(1,"%d ",{tree[VALUE]})
    end if
end procedure

procedure level_order(object tree, sequence more = {})
    if sequence(tree) then
        more &= {tree[LEFT],tree[RIGHT]}
        printf(1,"%d ",{tree[VALUE]})
    end if
    if length(more) > 0 then
        level_order(more[1],more[2..$])
    end if
end procedure

puts(1,"\n preorder:    ")  preorder(tree)
puts(1,"\n inorder:     ")  inorder(tree)
puts(1,"\n postorder:   ")  postorder(tree)
puts(1,"\n level-order: ")  level_order(tree)

{{out}}

 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

PHP

class Node {
    private $left;
    private $right;
    private $value;

    function __construct($value) {
        $this->value = $value;
    }

    public function getLeft() {
        return $this->left;
    }
    public function getRight() {
        return $this->right;
    }
    public function getValue() {
        return $this->value;
    }

    public function setLeft($value) {
        $this->left = $value;
    }
    public function setRight($value) {
        $this->right = $value;
    }
    public function setValue($value) {
        $this->value = $value;
    }
}

class TreeTraversal {

    public function preOrder(Node $n) {
        echo $n->getValue() . " ";
        if($n->getLeft() != null) {
            $this->preOrder($n->getLeft());
        }
        if($n->getRight() != null){
            $this->preOrder($n->getRight());
        }
    }

    public function inOrder(Node $n) {
        if($n->getLeft() != null) {
            $this->inOrder($n->getLeft());
        }
        echo $n->getValue() . " ";
        if($n->getRight() != null){
            $this->inOrder($n->getRight());
        }

    }

    public function postOrder(Node $n) {
        if($n->getLeft() != null) {
            $this->postOrder($n->getLeft());
        }
        if($n->getRight() != null){
            $this->postOrder($n->getRight());
        }
        echo $n->getValue() . " ";
    }

    public function levelOrder($arg) {
        $q[] = $arg;
        while (!empty($q)) {
            $n = array_shift($q);
            echo $n->getValue() . " ";
            if($n->getLeft() != null) {
                $q[] = $n->getLeft();
            }
            if($n->getRight() != null){
                $q[] = $n->getRight();
            }
        }
    }
}

$arr = [];
for ($i=1; $i < 10; $i++) {
    $arr[$i] = new Node($i);
}

$arr[6]->setLeft($arr[8]);
$arr[6]->setRight($arr[9]);
$arr[3]->setLeft($arr[6]);
$arr[4]->setLeft($arr[7]);
$arr[2]->setLeft($arr[4]);
$arr[2]->setRight($arr[5]);
$arr[1]->setLeft($arr[2]);
$arr[1]->setRight($arr[3]);

$tree = new TreeTraversal($arr);

echo "preorder:\t";
$tree->preOrder($arr[1]);
echo "\ninorder:\t";
$tree->inOrder($arr[1]);
echo "\npostorder:\t";
$tree->postOrder($arr[1]);
echo "\nlevel-order:\t";
$tree->levelOrder($arr[1]);

Output:

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

PicoLisp

(de preorder (Node Fun)
   (when Node
      (Fun (car Node))
      (preorder (cadr Node) Fun)
      (preorder (caddr Node) Fun) ) )

(de inorder (Node Fun)
   (when Node
      (inorder (cadr Node) Fun)
      (Fun (car Node))
      (inorder (caddr Node) Fun) ) )

(de postorder (Node Fun)
   (when Node
      (postorder (cadr Node) Fun)
      (postorder (caddr Node) Fun)
      (Fun (car Node)) ) )

(de level-order (Node Fun)
   (for (Q (circ Node)  Q)
      (let N (fifo 'Q)
         (Fun (car N))
         (and (cadr N) (fifo 'Q @))
         (and (caddr N) (fifo 'Q @)) ) ) )

(setq *Tree
   (1
      (2 (4 (7)) (5))
      (3 (6 (8) (9))) ) )

(for Order '(preorder inorder postorder level-order)
   (prin (align -13 (pack Order ":")))
   (Order *Tree printsp)
   (prinl) )

Output:

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

Prolog

Works with SWI-Prolog.

tree :-
	Tree= [1,
	        [2,
		   [4,
		     [7, nil, nil],
		     nil],
		   [5, nil, nil]],
	        [3,
		 [6,
		   [8, nil, nil],
		   [9,nil, nil]],
		 nil]],

	write('preorder    : '), preorder(Tree), nl,
	write('inorder     : '), inorder(Tree), nl,
	write('postorder   : '), postorder(Tree), nl,
	write('level-order : '), level_order([Tree]).

preorder(nil).
preorder([Node, FG, FD]) :-
	format('~w ', [Node]),
	preorder(FG),
	preorder(FD).


inorder(nil).
inorder([Node, FG, FD]) :-
	inorder(FG),
	format('~w ', [Node]),
	inorder(FD).

postorder(nil).
postorder([Node, FG, FD]) :-
	postorder(FG),
	postorder(FD),
	format('~w ', [Node]).


level_order([]).

level_order(A) :-
	level_order_(A, U-U, S),
	level_order(S).

level_order_([], S-[],S).

level_order_([[Node, FG, FD] | T], CS, FS) :-
	format('~w ', [Node]),
	append_dl(CS, [FG, FD|U]-U, CS1),
	level_order_(T, CS1, FS).

level_order_([nil | T], CS, FS) :-
	level_order_(T, CS, FS).


append_dl(X-Y, Y-Z, X-Z).

Output :

?- tree.
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
true .

PureBasic

{{works with|PureBasic|4.5+}}

Structure node
  value.i
  *left.node
  *right.node
EndStructure

Structure queue
  List q.i()
EndStructure

DataSection
  tree:
  Data.s "1(2(4(7),5),3(6(8,9)))"
EndDataSection

;Convenient routine to interpret string data to construct a tree of integers.
Procedure createTree(*n.node, *tPtr.Character)
  Protected num.s, *l.node, *ntPtr.Character

  Repeat
    Select *tPtr\c
      Case '0' To '9'
        num + Chr(*tPtr\c)
      Case '('
        *n\value = Val(num): num = ""
        *ntPtr = *tPtr + 1
        If *ntPtr\c = ','
          ProcedureReturn *tPtr
        Else
          *l = AllocateMemory(SizeOf(node))
          *n\left = *l: *tPtr = createTree(*l, *ntPtr)
        EndIf
      Case ')', ',', #Null
        If num: *n\value = Val(num): EndIf
        ProcedureReturn *tPtr
    EndSelect

    If *tPtr\c = ','
      *l = AllocateMemory(SizeOf(node)):
      *n\right = *l: *tPtr = createTree(*l, *tPtr + 1)
    EndIf
    *tPtr + 1
  ForEver
EndProcedure

Procedure enqueue(List q.i(), element)
  LastElement(q())
  AddElement(q())
  q() = element
EndProcedure

Procedure dequeue(List q.i())
  Protected element
  If FirstElement(q())
    element = q()
    DeleteElement(q())
  EndIf
  ProcedureReturn element
EndProcedure

Procedure onVisit(*n.node)
  Print(Str(*n\value) + " ")
EndProcedure

Procedure preorder(*n.node) ;recursive
  onVisit(*n)
  If *n\left
    preorder(*n\left)
  EndIf
  If *n\right
    preorder(*n\right)
  EndIf
EndProcedure

Procedure inorder(*n.node) ;recursive
  If *n\left
    inorder(*n\left)
  EndIf
  onVisit(*n)
  If *n\right
    inorder(*n\right)
  EndIf
EndProcedure

Procedure postorder(*n.node) ;recursive
  If *n\left
    postorder(*n\left)
  EndIf
  If *n\right
    postorder(*n\right)
  EndIf
  onVisit(*n)
EndProcedure

Procedure levelorder(*n.node)
  Dim q.queue(1)
  Protected readQueue = 1, writeQueue, *currNode.node

  enqueue(q(writeQueue)\q(),*n) ;start queue off with root
  Repeat
    readQueue ! 1: writeQueue ! 1
    While ListSize(q(readQueue)\q())
      *currNode = dequeue(q(readQueue)\q())
      If *currNode\left
        enqueue(q(writeQueue)\q(),*currNode\left)
      EndIf
      If *currNode\right
        enqueue(q(writeQueue)\q(),*currNode\right)
      EndIf
      onVisit(*currNode)
    Wend
  Until ListSize(q(writeQueue)\q()) = 0
EndProcedure

If OpenConsole()
  Define root.node
  createTree(root,?tree)

  Print("preorder: ")
  preorder(root)
  PrintN("")
  Print("inorder: ")
  inorder(root)
  PrintN("")
  Print("postorder: ")
  postorder(root)
  PrintN("")
  Print("levelorder: ")
  levelorder(root)
  PrintN("")

  Print(#CRLF$ + #CRLF$ + "Press ENTER to exit")
  Input()
  CloseConsole()
EndIf

Sample output:

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
levelorder: 1 2 3 4 5 6 7 8 9

Python

Python: Procedural

from collections import namedtuple

Node = namedtuple('Node', 'data, left, right')
tree = Node(1,
            Node(2,
                 Node(4,
                      Node(7, None, None),
                      None),
                 Node(5, None, None)),
            Node(3,
                 Node(6,
                      Node(8, None, None),
                      Node(9, None, None)),
                 None))

def printwithspace(i):
    print(i, end=' ')

def dfs(order, node, visitor):
    if node is not None:
        for action in order:
            if action == 'N':
                visitor(node.data)
            elif action == 'L':
                dfs(order, node.left, visitor)
            elif action == 'R':
                dfs(order, node.right, visitor)

def preorder(node, visitor = printwithspace):
    dfs('NLR', node, visitor)

def inorder(node, visitor = printwithspace):
    dfs('LNR', node, visitor)

def postorder(node, visitor = printwithspace):
    dfs('LRN', node, visitor)

def ls(node, more, visitor, order='TB'):
    "Level-based Top-to-Bottom or Bottom-to-Top tree search"
    if node:
        if more is None:
            more = []
        more += [node.left, node.right]
    for action in order:
        if action == 'B' and more:
            ls(more[0], more[1:], visitor, order)
        elif action == 'T' and node:
            visitor(node.data)

def levelorder(node, more=None, visitor = printwithspace):
    ls(node, more, visitor, 'TB')

# Because we can
def reverse_preorder(node, visitor = printwithspace):
    dfs('RLN', node, visitor)

def bottom_up_order(node, more=None, visitor = printwithspace, order='BT'):
    ls(node, more, visitor, 'BT')


if __name__ == '__main__':
    w = 10
    for traversal in [preorder, inorder, postorder, levelorder,
                      reverse_preorder, bottom_up_order]:
        if traversal == reverse_preorder:
            w = 20
            print('\nThe generalisation of function dfs allows:')
        if traversal == bottom_up_order:
            print('The generalisation of function ls allows:')
        print(f"{traversal.__name__:>{w}}:", end=' ')
        traversal(tree)
        print()

'''Sample output:'''

  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
levelorder: 1 2 3 4 5 6 7 8 9

The generalisation of function dfs allows:
    reverse_preorder: 9 8 6 3 5 7 4 2 1
The generalisation of function ls allows:
     bottom_up_order: 9 8 7 6 5 4 3 2 1

Python: Class based

Subclasses a namedtuple adding traversal methods that apply a visitor function to data at nodes of the tree in order

from collections import namedtuple
from sys import stdout

class Node(namedtuple('Node', 'data, left, right')):
    __slots__ = ()

    def preorder(self, visitor):
        if self is not None:
            visitor(self.data)
            Node.preorder(self.left, visitor)
            Node.preorder(self.right, visitor)

    def inorder(self, visitor):
        if self is not None:
            Node.inorder(self.left, visitor)
            visitor(self.data)
            Node.inorder(self.right, visitor)

    def postorder(self, visitor):
        if self is not None:
            Node.postorder(self.left, visitor)
            Node.postorder(self.right, visitor)
            visitor(self.data)

    def levelorder(self, visitor, more=None):
        if self is not None:
            if more is None:
                more = []
            more += [self.left, self.right]
            visitor(self.data)
        if more:
            Node.levelorder(more[0], visitor, more[1:])


def printwithspace(i):
    stdout.write("%i " % i)


tree = Node(1,
            Node(2,
                 Node(4,
                      Node(7, None, None),
                      None),
                 Node(5, None, None)),
            Node(3,
                 Node(6,
                      Node(8, None, None),
                      Node(9, None, None)),
                 None))


if __name__ == '__main__':
    stdout.write('  preorder: ')
    tree.preorder(printwithspace)
    stdout.write('\n   inorder: ')
    tree.inorder(printwithspace)
    stdout.write('\n postorder: ')
    tree.postorder(printwithspace)
    stdout.write('\nlevelorder: ')
    tree.levelorder(printwithspace)
    stdout.write('\n')

{{out}} As above.

===Python: Composition of pure (curried) functions===

Currying by default is probably not particularly 'Pythonic', but it does work well with higher-order functions – giving us more flexibility in compositional structure. It also often protects us from over-proliferation of the slightly noisy '''lambda''' keyword. (See for example the use of the curried version of '''map''' in the code below).

The approach taken here is to focus on the evaluation of expressions, rather than the sequencing of procedures. To keep evaluation simple and easily rearranged, mutation is stripped back wherever possible, and 'pure' functions, with inputs and outputs but, ideally, with no side-effects (and no sensitivities to global variables) are the basic building-block.

Composing pure functions also works well with library-building and code reuse – the literature on functional programming (particularly in the ML / OCaml / Haskell tradition) is rich in reusable abstractions for our toolkit. Some of them have already been absorbed, with standard or adjusted names, into the Python itertools module. (See the itertools module preface, and the '''takewhile''' function below).

Here, for example, for the '''pre-''', '''in-''' and '''post-''' orders, we can define a very general and reusable '''foldTree''' (a catamorphism over trees rather than lists) and just pass 3 different (rather simple) sequencing functions to it.

This level of abstraction and reuse brings real efficiencies – the short and easily-written '''foldTree''', for example, doesn't just traverse and list contents in flexible orders - we can pass all kinds of things to it. For the '''sum''' of all the numbers in the tree, we could write:

'''Tree traversals'''

from itertools import (chain, takewhile)
from functools import (reduce)
from operator import (mul)


# foldTree :: (a -> [b] -> b) -> Tree a -> b
def foldTree(f):
    '''The catamorphism on trees.
       A summary value derived by a depth-first fold.'''
    def go(node):
        return f(root(node))(
            list(map(go, nest(node)))
        )
    return lambda tree: go(tree)


# levels :: Tree a -> [[a]]
def levels(tree):
    '''A list of the nodes at each level of the tree.'''
    fmap = curry(map)
    return list(fmap(fmap(root))(
        takewhile(
            bool,
            iterate(concatMap(nest))([tree])
        )
    ))


# preorder :: a -> [[a]] -> [a]
def preorder(x):
    '''This node followed by the rest.'''
    return lambda xs: [x] + concat(xs)


# inorder :: a -> [[a]] -> [a]
def inorder(x):
    '''Descendants of any first child,
       then this node, then the rest.'''
    return lambda xs: (
        xs[0] + [x] + concat(xs[1:]) if xs else [x]
    )


# postorder :: a -> [[a]] -> [a]
def postorder(x):
    '''Descendants first, then this node.'''
    return lambda xs: concat(xs) + [x]


# levelorder :: Tree a -> [a]
def levelorder(tree):
    '''Top-down concatenation of this node
       with the rows below.'''
    return concat(levels(tree))


# treeSum :: Tree Int -> Int
def treeSum(x):
    '''This node's value + the sum of its descendants.'''
    return lambda xs: x + sum(xs)


# treeSum :: Tree Int -> Int
def treeProduct(x):
    '''This node's value * the product of its descendants.'''
    return lambda xs: x * numericProduct(xs)


# treeMax :: Tree Int -> Int
def treeMax(x):
    '''Maximum value of this node and any descendants.'''
    return lambda xs: max([x] + xs)


# treeMin :: Tree Int -> Int
def treeMin(x):
    '''Minimum value of this node and any descendants.'''
    return lambda xs: min([x] + xs)


# nodeCount :: Tree a -> Int
def nodeCount(_):
    '''One more than the total number of descendants.'''
    return lambda xs: 1 + sum(xs)


# treeWidth :: Tree a -> Int
def treeWidth(_):
    '''Sum of widths of any children, or a minimum of 1.'''
    return lambda xs: sum(xs) if xs else 1


# treeDepth :: Tree a -> Int
def treeDepth(_):
    '''One more than that of the deepest child.'''
    return lambda xs: 1 + (max(xs) if xs else 0)


# TEST ----------------------------------------------------
# main :: IO ()
def main():
    '''Tree traversals - accumulating and folding'''

    # tree :: Tree Int
    tree = Node(1)([
        Node(2)([
            Node(4)([
                Node(7)([])
            ]),
            Node(5)([])
        ]),
        Node(3)([
            Node(6)([
                Node(8)([]),
                Node(9)([])
            ])
        ])
    ])

    print(
        fTable(main.__doc__ + ':\n')(fName)(str)(
            lambda f: (
                foldTree(f) if 'levelorder' != fName(f) else f
            )(tree)
        )([
            preorder, inorder, postorder, levelorder,
            treeSum, treeProduct, treeMin, treeMax,
            nodeCount, treeWidth, treeDepth
        ])
    )


# GENERIC -------------------------------------------------

# Node :: a -> [Tree a] -> Tree a
def Node(v):
    '''Contructor for a Tree node which connects a
       value of some kind to a list of zero or
       more child trees.'''
    return lambda xs: {'type': 'Node', 'root': v, 'nest': xs}


# nest :: Tree a -> [Tree a]
def nest(tree):
    '''Accessor function for children of tree node'''
    return tree['nest'] if 'nest' in tree else None


# root :: Dict -> a
def root(tree):
    '''Accessor function for data of tree node'''
    return tree['root'] if 'root' in tree else None


# concat :: [[a]] -> [a]
# concat :: [String] -> String
def concat(xxs):
    '''The concatenation of all the elements in a list.'''
    xs = list(chain.from_iterable(xxs))
    unit = '' if isinstance(xs, str) else []
    return unit if not xs else (
        ''.join(xs) if isinstance(xs[0], str) else xs
    )


# concatMap :: (a -> [b]) -> [a] -> [b]
def concatMap(f):
    '''Concatenated list over which a function has been mapped.
       The list monad can be derived by using a function f which
       wraps its output a in list,
       (using an empty list to represent computational failure).'''
    return lambda xs: list(
        chain.from_iterable(
            map(f, xs)
        )
    )


# curry :: ((a, b) -> c) -> a -> b -> c
def curry(f):
    '''A curried function derived
       from an uncurried function.'''
    return lambda a: lambda b: f(a, b)


# iterate :: (a -> a) -> a -> Gen [a]
def iterate(f):
    '''An infinite list of repeated applications of f to x.'''
    def go(x):
        v = x
        while True:
            yield v
            v = f(v)
    return lambda x: go(x)


# numericProduct :: [Num] -> Num
def numericProduct(xs):
    '''The arithmetic product of all numbers in xs.'''
    return reduce(mul, xs, 1)


# FORMATTING ----------------------------------------------

# fName :: (a -> b) -> String
def fName(f):
    '''The name bound to the function.'''
    return f.__name__


# fTable :: String -> (a -> String) ->
#                     (b -> String) -> (a -> b) -> [a] -> String
def fTable(s):
    '''Heading -> x display function -> fx display function ->
                     f -> xs -> tabular string.
    '''
    def go(xShow, fxShow, f, xs):
        ys = [xShow(x) for x in xs]
        w = max(map(len, ys))
        return s + '\n' + '\n'.join(map(
            lambda x, y: y.rjust(w, ' ') + ' -> ' + fxShow(f(x)),
            xs, ys
        ))
    return lambda xShow: lambda fxShow: lambda f: lambda xs: go(
        xShow, fxShow, f, xs
    )


if __name__ == '__main__':
    main()

{{Out}}

Tree traversals - accumulating and folding:

   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]
 levelorder -> [1, 2, 3, 4, 5, 6, 7, 8, 9]
    treeSum -> 45
treeProduct -> 362880
    treeMin -> 1
    treeMax -> 9
  nodeCount -> 9
  treeWidth -> 4
  treeDepth -> 4

Qi

(set *tree* [1 [2 [4 [7]]
                  [5]]
               [3 [6 [8]
                     [9]]]])

(define inorder
  []      -> []
  [V]     -> [V]
  [V L]   -> (append (inorder L)
                     [V])
  [V L R] -> (append (inorder L)
                     [V]
                     (inorder R)))

(define postorder
  []      -> []
  [V]     -> [V]
  [V L]   -> (append (postorder L)
                     [V])
  [V L R] -> (append (postorder L)
                     (postorder R)
                     [V]))

(define preorder
  []      -> []
  [V]     -> [V]
  [V L]   -> (append [V]
                     (preorder L))
  [V L R] -> (append [V]
                     (preorder L)
                     (preorder R)))

(define levelorder-0
  []             -> []
  [[]       | Q] -> (levelorder-0 Q)
  [[V | LR] | Q] -> [V | (levelorder-0 (append Q LR))])

(define levelorder
  Node -> (levelorder-0 [Node]))

(preorder (value *tree*))
(postorder (value *tree*))
(inorder (value *tree*))
(levelorder (value *tree*))

Output:

[1 2 4 7 5 3 6 8 9]
[7 4 2 5 1 8 6 9 3]
[7 4 5 2 8 9 6 3 1]
[1 2 3 4 5 6 7 8 9]

Racket

#lang racket

(define the-tree ; Node: (list <data> <left> <right>)
  '(1 (2 (4 (7 #f #f) #f) (5 #f #f)) (3 (6 (8 #f #f) (9 #f #f)) #f)))

(define (preorder tree visit)
  (let loop ([t tree])
    (when t (visit (car t)) (loop (cadr t)) (loop (caddr t)))))
(define (inorder tree visit)
  (let loop ([t tree])
    (when t (loop (cadr t)) (visit (car t)) (loop (caddr t)))))
(define (postorder tree visit)
  (let loop ([t tree])
    (when t (loop (cadr t)) (loop (caddr t)) (visit (car t)))))
(define (levelorder tree visit)
  (let loop ([trees (list tree)])
    (unless (null? trees)
      ((compose1 loop (curry filter values) append*)
       (for/list ([t trees] #:when t) (visit (car t)) (cdr t))))))

(define (run order)
  (printf "~a:" (object-name order))
  (order the-tree (λ(x) (printf " ~s" x)))
  (newline))
(for-each run (list preorder inorder postorder levelorder))

Output:

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
levelorder: 1 2 3 4 5 6 7 8 9

REXX

/* REXX ***************************************************************
* Tree traversal
=           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
=  level-order: 1 2 3 4 5 6 7 8 9
=  postorder:   7 4 5 2 8 9 6 3 1
=  inorder:     7 4 2 5 1 8 6 9 3

* 17.06.2012 Walter Pachl not thoroughly tested
**********************************************************************/
debug=0
wl_soll=1 2 4 7 5 3 6 8 9
il_soll=7 4 2 5 1 8 6 9 3
pl_soll=7 4 5 2 8 9 6 3 1
ll_soll=1 2 3 4 5 6 7 8 9

Call mktree
wl.=''; wl='' /* preorder    */
ll.=''; ll='' /* level-order */
        il='' /* inorder     */
        pl='' /* postorder   */

/**********************************************************************
* First walk the tree and construct preorder and level-order lists
**********************************************************************/
done.=0
lvl=1
z=root
Call note z
Do Until z=0
  z=go_next(z)
  Call note z
  End
Call show 'preorder:   ',wl,wl_soll
Do lvl=1 To 4
  ll=ll ll.lvl
  End
Call show 'level-order:',ll,ll_soll

/**********************************************************************
* Next construct postorder list
**********************************************************************/
done.=0
ridone.=0
z=lbot(root)
Call notep z
Do Until z=0
  br=brother(z)
  If br>0 &,
     done.br=0 Then Do
    ridone.br=1
    z=lbot(br)
    Call notep z
    End
  Else
  z=father(z)
  Call notep z
  End
Call show 'postorder:  ',pl,pl_soll

/**********************************************************************
* Finally construct inorder list
**********************************************************************/
done.=0
ridone.=0
z=lbot(root)
Call notei z
Do Until z=0
  z=father(z)
  Call notei z
  ri=node.z.0rite
  If ridone.z=0 Then Do
    ridone.z=1
    If ri>0 Then Do
      z=lbot(ri)
      Call notei z
      End
    End
  End

/**********************************************************************
* And now show the results and check them for correctness
**********************************************************************/
Call show 'inorder:    ',il,il_soll

Exit

show: Parse Arg Which,have,soll
/**********************************************************************
* Show our result and show it it's correct
**********************************************************************/
have=space(have)
If have=soll Then
  tag=''
Else
  tag='*wrong*'
Say which have tag
If tag<>'' Then
  Say '------------>'soll 'is the expected result'
Return

brother: Procedure Expose node.
/**********************************************************************
* Return the right node of this node's father or 0
**********************************************************************/
  Parse arg no
  nof=node.no.0father
  brot1=node.nof.0rite
  Return brot1

notei: Procedure Expose debug il done.
/**********************************************************************
* append the given node to il
**********************************************************************/
  Parse Arg nd
  If nd<>0 &,
     done.nd=0 Then
    il=il nd
  If debug Then
    Say 'notei' nd
  done.nd=1
  Return

notep: Procedure Expose debug pl done.
/**********************************************************************
* append the given node to pl
**********************************************************************/
  Parse Arg nd
  If nd<>0 &,
     done.nd=0 Then Do
    pl=pl nd
    If debug Then
      Say 'notep' nd
    End
  done.nd=1
  Return

father: Procedure Expose node.
/**********************************************************************
* Return the father of the argument
* or 0 if the root is given as argument
**********************************************************************/
  Parse Arg nd
  Return node.nd.0father

lbot: Procedure Expose node.
/**********************************************************************
* From node z: Walk down on the left side until you reach the bottom
* and return the bottom node
* If z has no left son (at the bottom of the tree) returm itself
**********************************************************************/
  Parse Arg z
  Do i=1 To 100
    If node.z.0left<>0 Then
      z=node.z.0left
    Else
      Leave
    End
  Return z

note:
/**********************************************************************
* add the node to the preorder list unless it's already there
* add the node to the level list
**********************************************************************/
  If z<>0 &,                           /* it's a node                */
     done.z=0 Then Do                  /* not yet done               */
    wl=wl z                            /* add it to the preorder list*/
    ll.lvl=ll.lvl z                    /* add it to the level list   */
    done.z=1                           /* remember it's done         */
    End
  Return

go_next: Procedure Expose node. lvl
/**********************************************************************
* find the next node to visit in the treewalk
**********************************************************************/
  next=0
  Parse arg z
  If node.z.0left<>0 Then Do           /* there is a left son        */
    If node.z.0left.done=0 Then Do     /* we have not visited it     */
      next=node.z.0left                /* so we go there             */
      node.z.0left.done=1              /* note we were here          */
      lvl=lvl+1                        /* increase the level         */
      End
    End
  If next=0 Then Do                    /* not moved yet              */
    If node.z.0rite<>0 Then Do         /* there is a right son       */
      If node.z.0rite.done=0 Then Do   /* we have not visited it     */
        next=node.z.0rite              /* so we go there             */
        node.z.0rite.done=1            /* note we were here          */
        lvl=lvl+1                      /* increase the level         */
        End
      End
    End
  If next=0 Then Do                    /* not moved yet              */
    next=node.z.0father                /* go to the father           */
    lvl=lvl-1                          /* decrease the level         */
    End
  Return next                          /* that's the next node       */
                                       /* or zero if we are done     */

mknode: Procedure Expose node.
/**********************************************************************
* create a new node
**********************************************************************/
  Parse Arg name
  z=node.0+1
  node.z.0name=name
  node.z.0father=0
  node.z.0left  =0
  node.z.0rite  =0
  node.0=z
  Return z                        /* number of the node just created */

attleft: Procedure Expose node.
/**********************************************************************
* make son the left son of father
**********************************************************************/
  Parse Arg son,father
  node.son.0father=father
  z=node.father.0left
  If z<>0 Then Do
    node.z.0father=son
    node.son.0left=z
    End
  node.father.0left=son
  Return

attrite: Procedure Expose node.
/**********************************************************************
* make son the right son of father
**********************************************************************/
  Parse Arg son,father
  node.son.0father=father
  z=node.father.0rite
  If z<>0 Then Do
    node.z.0father=son
    node.son.0rite=z
    End
  node.father.0rite=son
  le=node.father.0left
  If le>0 Then
    node.le.0brother=node.father.0rite
  Return

mktree: Procedure Expose node. root
/**********************************************************************
* build the tree according to the task
**********************************************************************/
  node.=0
  a=mknode('A'); root=a
  b=mknode('B'); Call attleft b,a
  c=mknode('C'); Call attrite c,a
  d=mknode('D'); Call attleft d,b
  e=mknode('E'); Call attrite e,b
  f=mknode('F'); Call attleft f,c
  g=mknode('G'); Call attleft g,d
  h=mknode('H'); Call attleft h,f
  i=mknode('I'); Call attrite i,f
  Call show_tree 1
  Return

show_tree: Procedure Expose node.
/**********************************************************************
* Show the tree
*         f
*     l1   1  r1
*   l   r   l   r
*  l r l r l r l r
* 12345678901234567890
**********************************************************************/
  Parse Arg f
  l.=''
                          l.1=overlay(f   ,l.1, 9)

  l1=node.f.0left        ;l.2=overlay(l1  ,l.2, 5)
/*b1=node.f.0brother     ;l.2=overlay(b1  ,l.2, 9) */
  r1=node.f.0rite        ;l.2=overlay(r1  ,l.2,13)

  l1g=node.l1.0left      ;l.3=overlay(l1g ,l.3, 3)
/*b1g=node.l1.0brother   ;l.3=overlay(b1g ,l.3, 5) */
  r1g=node.l1.0rite      ;l.3=overlay(r1g ,l.3, 7)

  l2g=node.r1.0left      ;l.3=overlay(l2g ,l.3,11)
/*b2g=node.r1.0brother   ;l.3=overlay(b2g ,l.3,13) */
  r2g=node.r1.0rite      ;l.3=overlay(r2g ,l.3,15)

  l1ls=node.l1g.0left    ;l.4=overlay(l1ls,l.4, 2)
/*b1ls=node.l1g.0brother ;l.4=overlay(b1ls,l.4, 3) */
  r1ls=node.l1g.0rite    ;l.4=overlay(r1ls,l.4, 4)

  l1rs=node.r1g.0left    ;l.4=overlay(l1rs,l.4, 6)
/*b1rs=node.r1g.0brother ;l.4=overlay(b1rs,l.4, 7) */
  r1rs=node.r1g.0rite    ;l.4=overlay(r1rs,l.4, 8)

  l2ls=node.l2g.0left    ;l.4=overlay(l2ls,l.4,10)
/*b2ls=node.l2g.0brother ;l.4=overlay(b2ls,l.4,11) */
  r2ls=node.l2g.0rite    ;l.4=overlay(r2ls,l.4,12)

  l2rs=node.r2g.0left    ;l.4=overlay(l2rs,l.4,14)
/*b2rs=node.r2g.0brother ;l.4=overlay(b2rs,l.4,15) */
  r2rs=node.r2g.0rite    ;l.4=overlay(r2rs,l.4,16)
  Do i=1 To 4
    Say translate(l.i,' ','0')
    Say ''
    End
  Return

{{out}}

        1

    2       3

  4   5   6

 7       8 9

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

Ruby

BinaryTreeNode = Struct.new(:value, :left, :right) do
  def self.from_array(nested_list)
    value, left, right = nested_list
    if value
      self.new(value, self.from_array(left), self.from_array(right))
    end
  end

  def walk_nodes(order, &block)
    order.each do |node|
      case node
      when :left  then left && left.walk_nodes(order, &block)
      when :self  then yield self
      when :right then right && right.walk_nodes(order, &block)
      end
    end
  end

  def each_preorder(&b)  walk_nodes([:self, :left, :right], &b) end
  def each_inorder(&b)   walk_nodes([:left, :self, :right], &b) end
  def each_postorder(&b) walk_nodes([:left, :right, :self], &b) end

  def each_levelorder
    queue = [self]
    until queue.empty?
      node = queue.shift
      yield node
      queue << node.left if node.left
      queue << node.right if node.right
    end
  end
end

root = BinaryTreeNode.from_array [1, [2, [4, 7], [5]], [3, [6, [8], [9]]]]

BinaryTreeNode.instance_methods.select{|m| m=~/.+order/}.each do |mthd|
  printf "%-11s ", mthd[5..-1] + ':'
  root.send(mthd) {|node| print "#{node.value} "}
  puts
end

{{out}}

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
levelorder: 1 2 3 4 5 6 7 8 9

Rust

This solution uses iteration (rather than recursion) for all traversal types.

#![feature(box_syntax, box_patterns)]

use std::collections::VecDeque;

#[derive(Debug)]
struct TreeNode<T> {
    value: T,
    left: Option<Box<TreeNode<T>>>,
    right: Option<Box<TreeNode<T>>>,
}

enum TraversalMethod {
    PreOrder,
    InOrder,
    PostOrder,
    LevelOrder,
}

impl<T> TreeNode<T> {
    pub fn new(arr: &[[i8; 3]]) -> TreeNode<i8> {

        let l = match arr[0][1] {
            -1 => None,
            i @ _ => Some(Box::new(TreeNode::<i8>::new(&arr[(i - arr[0][0]) as usize..]))),
        };
        let r = match arr[0][2] {
            -1 => None,
            i @ _ => Some(Box::new(TreeNode::<i8>::new(&arr[(i - arr[0][0]) as usize..]))),
        };

        TreeNode {
            value: arr[0][0],
            left: l,
            right: r,
        }
    }

    pub fn traverse(&self, tr: &TraversalMethod) -> Vec<&TreeNode<T>> {
        match tr {
            &TraversalMethod::PreOrder => self.iterative_preorder(),
            &TraversalMethod::InOrder => self.iterative_inorder(),
            &TraversalMethod::PostOrder => self.iterative_postorder(),
            &TraversalMethod::LevelOrder => self.iterative_levelorder(),
        }
    }

    fn iterative_preorder(&self) -> Vec<&TreeNode<T>> {
        let mut stack: Vec<&TreeNode<T>> = Vec::new();
        let mut res: Vec<&TreeNode<T>> = Vec::new();

        stack.push(self);
        while !stack.is_empty() {
            let node = stack.pop().unwrap();
            res.push(node);
            match node.right {
                None => {}
                Some(box ref n) => stack.push(n),
            }
            match node.left {
                None => {}
                Some(box ref n) => stack.push(n),
            }
        }
        res
    }

    // Leftmost to rightmost
    fn iterative_inorder(&self) -> Vec<&TreeNode<T>> {
        let mut stack: Vec<&TreeNode<T>> = Vec::new();
        let mut res: Vec<&TreeNode<T>> = Vec::new();
        let mut p = self;

        loop {
            // Stack parents and right children while left-descending
            loop {
                match p.right {
                    None => {}
                    Some(box ref n) => stack.push(n),
                }
                stack.push(p);
                match p.left {
                    None => break,
                    Some(box ref n) => p = n,
                }
            }
            // Visit the nodes with no right child
            p = stack.pop().unwrap();
            while !stack.is_empty() && p.right.is_none() {
                res.push(p);
                p = stack.pop().unwrap();
            }
            // First node that can potentially have a right child:
            res.push(p);
            if stack.is_empty() {
                break;
            } else {
                p = stack.pop().unwrap();
            }
        }
        res
    }

    // Left-to-right postorder is same sequence as right-to-left preorder, reversed
    fn iterative_postorder(&self) -> Vec<&TreeNode<T>> {
        let mut stack: Vec<&TreeNode<T>> = Vec::new();
        let mut res: Vec<&TreeNode<T>> = Vec::new();

        stack.push(self);
        while !stack.is_empty() {
            let node = stack.pop().unwrap();
            res.push(node);
            match node.left {
                None => {}
                Some(box ref n) => stack.push(n),
            }
            match node.right {
                None => {}
                Some(box ref n) => stack.push(n),
            }
        }
        let rev_iter = res.iter().rev();
        let mut rev: Vec<&TreeNode<T>> = Vec::new();
        for elem in rev_iter {
            rev.push(elem);
        }
        rev
    }

    fn iterative_levelorder(&self) -> Vec<&TreeNode<T>> {
        let mut queue: VecDeque<&TreeNode<T>> = VecDeque::new();
        let mut res: Vec<&TreeNode<T>> = Vec::new();

        queue.push_back(self);
        while !queue.is_empty() {
            let node = queue.pop_front().unwrap();
            res.push(node);
            match node.left {
                None => {}
                Some(box ref n) => queue.push_back(n),
            }
            match node.right {
                None => {}
                Some(box ref n) => queue.push_back(n),
            }
        }
        res
    }
}

fn main() {
    // Array representation of task tree
    let arr_tree = [[1, 2, 3],
                    [2, 4, 5],
                    [3, 6, -1],
                    [4, 7, -1],
                    [5, -1, -1],
                    [6, 8, 9],
                    [7, -1, -1],
                    [8, -1, -1],
                    [9, -1, -1]];

    let root = TreeNode::<i8>::new(&arr_tree);

    for method_label in [(TraversalMethod::PreOrder, "pre-order:"),
                         (TraversalMethod::InOrder, "in-order:"),
                         (TraversalMethod::PostOrder, "post-order:"),
                         (TraversalMethod::LevelOrder, "level-order:")]
                            .iter() {
        print!("{}\t", method_label.1);
        for n in root.traverse(&method_label.0) {
            print!(" {}", n.value);
        }
        print!("\n");
    }
}