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>

Erlang

<lang erlang> -module(tree_traversal). -export([main/0]). -export([preorder/2, inorder/2, postorder/2, levelorder/2]). -export([tnode/0, tnode/1, tnode/3]).

-define(NEWLINE, io:format("~n")).

tnode() -> {}. tnode(V) -> {node, V, {}, {}}. tnode(V,L,R) -> {node, V, L, R}.

preorder(_,{}) -> ok; preorder(F,{node,V,L,R}) ->

   F(V), preorder(F,L), preorder(F,R).

inorder(_,{}) -> ok; inorder(F,{node,V,L,R}) ->

   inorder(F,L), F(V), inorder(F,R).

postorder(_,{}) -> ok; postorder(F,{node,V,L,R}) ->

   postorder(F,L), postorder(F,R), F(V).

levelorder(_, []) -> []; levelorder(F, [{}|T]) -> levelorder(F, T); levelorder(F, [{node,V,L,R}|T]) ->

   F(V), levelorder(F, T++[L,R]);

levelorder(F, X) -> levelorder(F, [X]).

main() ->

   Tree = tnode(1,
                tnode(2,
                      tnode(4, tnode(7), tnode()),
                      tnode(5, tnode(), tnode())),
                tnode(3,
                      tnode(6, tnode(8), tnode(9)),
                      tnode())),
   F = fun(X) -> io:format("~p ",[X]) end,
   preorder(F, Tree), ?NEWLINE,
   inorder(F, Tree), ?NEWLINE,
   postorder(F, Tree), ?NEWLINE,
   levelorder(F, Tree), ?NEWLINE.

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

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

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

Required example:

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

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

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. (And n must be parenthesized if it is not a single word.)

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

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]
 pre.order node.left :tree :action
 invoke :action first :tree
 pre.order node.right :tree :action

end to post.order :tree :action

 if empty? :tree [stop]
 pre.order node.left :tree :action
 pre.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) </lang>

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, @left, @right = value, left, right
 end
 attr_reader :value, :left, :right

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

%w{each_preorder each_inorder each_postorder each_levelorder}.each {|mthd|

 printf "%-11s ", mthd[5..-1] + ':'
 root.send(mthd) {|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

Unix Shell

Bash (also "sh" on most Unix systems) has arrays. We implement a node as an association between three arrays: left, right, and value. <lang bash>left=() right=() value=()

node node#, left#, right#, value
if value is empty, use node#

node() {

 nx=${1:-'Missing node index'}
 leftx=${2}
 rightx=${3}
 val=${4:-$1}
 value[$nx]="$val"
 left[$nx]="$leftx"
 right[$nx]="$rightx"

}

define the tree

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

walk NODE# ORDER

walk() {

 local nx=${1-"Missing index"}
 shift
 for branch in "$@" ; do
   case "$branch" in
     left)  if [[ "${left[$nx]}" ]];      then walk ${left[$nx]}  $@ ; fi ;;
     right) if [[ "${right[$nx]}" ]];     then walk ${right[$nx]} $@ ; fi ;;
     self)  printf "%d " "${value[$nx]}"  ;;
   esac
 done

}

apush() {

 local var="$1"
 eval "$var=( \"\${$var[@]}\" \"$2\" )"

}

showname() {

 printf "%-12s " "$1:"

}

showdata() {

 showname "$1"
 shift
 walk "$@"
 echo

}

preorder() { showdata $FUNCNAME $1 self left right ; } inorder() { showdata $FUNCNAME $1 left self right ; } postorder() { showdata $FUNCNAME $1 left right self ; } levelorder() {

 showname 'level-order'
 queue=( $1 )
 x=0
 while [[ $x < ${#queue[*]} ]]; do
   value="${queue[$x]}"
   printf "%d " "$value"
   for more in "${left[$value]}" "${right[$value]}" ; do
     if -n "$more" ; then

apush queue "$more"

     fi
   done
   : $((x++))
 done
 echo

}

preorder 1 inorder 1 postorder 1 levelorder 1</lang> The output: <lang "bash">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 </lang>

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

Erlang

Forth

Haskell

J

Java

Logo

OCaml

Python

Ruby

Tcl

Unix Shell

Ursala