Tree traversal

Implement a binary tree where each node carries an integer, and implement preoder, inorder, postorder and level-order traversal. Use those traversals to output the following tree:

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

The correct output should look like this:

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

This article has more information on traversing trees.

Common Lisp

<lang lisp>(defun preorder (node f)

 (when node
   (funcall f (first node))
   (preorder (second node) f)
   (preorder (third node)  f)))

(defun inorder (node f)

 (when node
   (inorder (second node) f)
   (funcall f (first node))
   (inorder (third node)  f)))

(defun postorder (node f)

 (when node
   (postorder (second node) f)
   (funcall f (first node))
   (postorder (third node)  f)))

(defun level-order (node f)

 (loop with level = (list node)
       while level
       do
   (setf level (loop for node in level
                     when node
                       do (funcall f (first node))
                       and collect (second node)
                       and collect (third node)))))

(defparameter *tree* '(1 (2 (4 (7))

                           (5))
                        (3 (6 (8)
                              (9)))))

(defun show (traversal-function)

 (format t "~&~(~A~):~12,0T" traversal-function)
 (funcall traversal-function *tree* (lambda (value) (format t " ~A" value))))

(map nil #'show '(preorder inorder postorder level-order))</lang>

Output:

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

E

<lang e>def btree := [1, [2, [4, [7, null, null],

                        null],
                    [5, null, null]],
                [3, [6, [8, null, null],
                        [9, null, null]],
                    null]]

def backtrackingOrder(node, pre, mid, post) {

   switch (node) {
       match ==null {}
       match [value, left, right] {
           pre(value)
           backtrackingOrder(left, pre, mid, post)
           mid(value)
           backtrackingOrder(right, pre, mid, post)
           post(value)
       }
   }

}

def levelOrder(root, func) {

   var level := [root].diverge()
   while (level.size() > 0) {
       for node in level.removeRun(0) {
           switch (node) {
               match ==null {}
               match [value, left, right] {
                   func(value)
                   level.push(left)
                   level.push(right)

} } } } }

print("preorder: ") backtrackingOrder(btree, fn v { print(" ", v) }, fn _ {}, fn _ {}) println()

print("inorder: ") backtrackingOrder(btree, fn _ {}, fn v { print(" ", v) }, fn _ {}) println()

print("postorder: ") backtrackingOrder(btree, fn _ {}, fn _ {}, fn v { print(" ", v) }) println()

print("level-order:") levelOrder(btree, fn v { print(" ", v) }) println()</lang>

Forth

<lang forth> \ binary tree (dictionary)

node ( l r data -- node ) here >r , , , r> ;

leaf ( data -- node ) 0 0 rot node ;

>data ( node -- ) @ ;

>right ( node -- ) cell+ @ ;

>left ( node -- ) cell+ cell+ @ ;

preorder ( xt tree -- )

 dup 0= if 2drop exit then
 2dup >data swap execute
 2dup >left recurse
      >right recurse ;

inorder ( xt tree -- )

 dup 0= if 2drop exit then
 2dup >left recurse
 2dup >data swap execute
      >right recurse ;

postorder ( xt tree -- )

 dup 0= if 2drop exit then
 2dup >left recurse
 2dup >right recurse
      >data swap execute ;

max-depth ( tree -- n )

 dup 0= if exit then
 dup  >left recurse
 swap >right recurse max 1+ ;

defer depthaction

depthorder ( depth tree -- )

 dup 0= if 2drop exit then
 over 0=
 if   >data depthaction drop
 else over 1- over >left  recurse
      swap 1- swap >right recurse
 then ;

levelorder ( xt tree -- )

 swap is depthaction
 dup max-depth 0 ?do
   i over depthorder
 loop drop ;

7 leaf 0 4 node

             5 leaf 2 node

8 leaf 9 leaf 6 node

             0      3 node 1 node value tree

cr ' . tree preorder \ 1 2 4 7 5 3 6 8 9 cr ' . tree inorder \ 7 4 2 5 1 8 6 9 3 cr ' . tree postorder \ 7 4 5 2 8 9 6 3 1 cr tree max-depth . \ 4 cr ' . tree levelorder \ 1 2 3 4 5 6 7 8 9 </lang>

Haskell

<lang 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])

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 () main = do print $ preorder tree

         print $ inorder tree
         print $ postorder tree
         print $ levelorder tree</lang>

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]

J

tree=: 1;(2;(4;<<7);<<5);<3;<6;(<8);<<9

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

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 9 8 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 9 8 6 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

Java

Works with: Java version 1.5+

<lang java5>import java.util.Queue; import java.util.LinkedList; public class TreeTraverse {

   private static class Node<T>{
       public Node<T> left;
       public Node<T> right;
       public T data;
       
       public Node(T data){
           this.data = data;
       }

       public Node<T> getLeft() {
           return left;
       }

       public void setLeft(Node<T> left) {
           this.left = left;
       }

       public Node<T> getRight() {
           return right;
       }

       public void setRight(Node<T> right) {
           this.right = right;
       }
   }

   public static void preorder(Node<?> n){
       if (n != null) {
           System.out.print(n.data + " ");
           preorder(n.getLeft());
           preorder(n.getRight());
       }
   }
   
   public static void inorder(Node<?> n){
       if (n != null) {
           inorder(n.getLeft());
           System.out.print(n.data + " ");
           inorder(n.getRight());
       }
   }
   
   public static void postorder(Node<?> n){
       if (n != null){
           postorder(n.getLeft());
           postorder(n.getRight());
           System.out.print(n.data + " ");
       }
   }
   
   public static void levelorder(Node<?> n) {
       Queue<Node<?>> nodequeue = new LinkedList<Node<?>>();
       if (n != null)
           nodequeue.add(n);
       while (!nodequeue.isEmpty()) {
           Node<?> next = nodequeue.remove();
           System.out.print(next.data + " ");
           if (next.getLeft() != null) {
               nodequeue.add(next.getLeft());
           }
           if (next.getRight() != null) {
               nodequeue.add(next.getRight());
           }
       }
   }
   
   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.setLeft(two);
       one.setRight(three);
       two.setLeft(four);
       two.setRight(five);
       three.setLeft(six);
       four.setLeft(seven);
       six.setLeft(eight);
       six.setRight(nine);
       
       preorder(one);
       System.out.println();
       inorder(one);
       System.out.println();
       postorder(one);
       System.out.println();
       levelorder(one);
       System.out.println();
   }

}</lang> 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

OCaml

<lang 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) -> preorder f l;
                   preorder 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 ()</lang>

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

Python

<lang python> from collections import namedtuple from sys import stdout

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):

   stdout.write("%i " % i)

def preorder(node, visitor = printwithspace):

   if node is not None:
       visitor(node.data)
       preorder(node.left, visitor)
       preorder(node.right, visitor)

def inorder(node, visitor = printwithspace):

   if node is not None:
       inorder(node.left, visitor)
       visitor(node.data)
       inorder(node.right, visitor)

def postorder(node, visitor = printwithspace):

   if node is not None:
       postorder(node.left, visitor)
       postorder(node.right, visitor)
       visitor(node.data)

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

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

stdout.write(' preorder: ') preorder(tree) stdout.write('\n inorder: ') inorder(tree) stdout.write('\n postorder: ') postorder(tree) stdout.write('\nlevelorder: ') levelorder(tree) stdout.write('\n') </lang>

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

Ruby

<lang ruby>class BinaryTreeNode

 def initialize(value, left=nil, right=nil)
   @value = value
   @left = left
   @right = right
 end
 attr_reader :value, :left, :right

 def each_preorder(&block)
   yield self
   left.each_preorder(&block) if left
   right.each_preorder(&block) if right
 end

 def each_inorder(&block)
   left.each_inorder(&block) if left
   yield self
   right.each_inorder(&block) if right
 end

 def each_postorder(&block)
   left.each_postorder(&block) if left
   right.each_postorder(&block) if right
   yield self
 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.new(1,

         BinaryTreeNode.new(2,
           BinaryTreeNode.new(4,
             BinaryTreeNode.new(7)
           ),
           BinaryTreeNode.new(5)
         ),
         BinaryTreeNode.new(3,
           BinaryTreeNode.new(6,
             BinaryTreeNode.new(8),
             BinaryTreeNode.new(9)
           )
         )
       )

print "preorder: " root.each_preorder {|node| print "#{node.value} "} puts print "inorder: " root.each_inorder {|node| print "#{node.value} "} puts print "postorder: " root.each_postorder {|node| print "#{node.value} "} puts print "levelorder: " root.each_levelorder {|node| print "#{node.value} "} puts</lang> 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

Tcl

Works with: Tcl version 8.6

<lang tcl>oo::class create tree {

   # Basic tree data structure stuff...
   variable val l r
   constructor {value {left {}} {right {}}} {

set val $value set l $left set r $right

   }
   method value {} {return $val}
   method left  {} {return $l}
   method right {} {return $r}
   destructor {

if {$l ne ""} {$l destroy} if {$r ne ""} {$r destroy}

   # Traversal methods
   method preorder {varName script {level 0}} {

upvar [incr level] $varName var set var $val uplevel $level $script if {$l ne ""} {$l preorder $varName $script $level} if {$r ne ""} {$r preorder $varName $script $level}

   }
   method inorder {varName script {level 0}} {

upvar [incr level] $varName var if {$l ne ""} {$l inorder $varName $script $level} set var $val uplevel $level $script if {$r ne ""} {$r inorder $varName $script $level}

   }
   method postorder {varName script {level 0}} {

upvar [incr level] $varName var if {$l ne ""} {$l postorder $varName $script $level} if {$r ne ""} {$r postorder $varName $script $level} set var $val uplevel $level $script

   }
   method levelorder {varName script} {

upvar 1 $varName var set nodes [list [self]]; # A queue of nodes to process while {[llength $nodes] > 0} { set nodes [lassign $nodes n] set var [$n value] uplevel 1 $script if {[$n left] ne ""} {lappend nodes [$n left]} if {[$n right] ne ""} {lappend nodes [$n right]} }

}</lang> Note that in Tcl it is conventional to handle performing something “for each element” by evaluating a script in the caller's scope for each node after setting a caller-nominated variable to the value for that iteration. Doing this transparently while recursing requires the use of a varying ‘level’ parameter to upvar and uplevel, but makes for compact and clear code.

Demo code to satisfy the official challenge instance: <lang tcl># Helpers to make construction and listing of a whole tree simpler proc Tree nested {

   lassign $nested v l r
   if {$l ne ""} {set l [Tree $l]}
   if {$r ne ""} {set r [Tree $r]}
   tree new $v $l $r

} proc Listify {tree order} {

   set list {}
   $tree $order v {

lappend list $v

   }
   return $list

}

Make a tree, print it a few ways, and destroy the tree

set t [Tree {1 {2 {4 7} 5} {3 {6 8 9}}}] puts "preorder: [Listify $t preorder]" puts "inorder: [Listify $t inorder]" puts "postorder: [Listify $t postorder]" puts "level-order: [Listify $t levelorder]" $t destroy</lang> 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

Ursala

Ursala has built-in notation for trees and is perfect for whipping up little tree walking functions. <lang Ursala> tree =

1^:<

  2^: <4^: <7^: <>, 0>, 5^: <>>,
  3^: <6^: <8^: <>, 9^: <>>, 0>>

pre = ~&dvLPCo post = ~&vLPdNCTo in = ~&vvhPdvtL2CTiQo lev = ~&iNCaadSPfavSLiF3RTaq

cast %nLL

main = <.pre,in,post,lev> tree </lang> 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>>

Tree traversal

Ada

C

C++

Common Lisp

E

Forth

Haskell

J

Java

OCaml

Python

Ruby

Tcl

Ursala