Tree traversal

Tree traversal
You are encouraged to solve this task according to the task description, using any language you may know.

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.

Ada

<lang Ada>with Ada.Text_Io; use Ada.Text_Io; with Ada.Unchecked_Deallocation; with Ada.Containers.Doubly_Linked_Lists;

procedure Tree_Traversal is

  type Node;
  type Node_Access is access Node;
  type Node is record
     Left : Node_Access := null;
     Right : Node_Access := null;
     Data : Integer;
  end record;
  procedure Destroy_Tree(N : in out Node_Access) is
     procedure free is new Ada.Unchecked_Deallocation(Node, Node_Access);
  begin
     if N.Left /= null then
        Destroy_Tree(N.Left);
     end if;
     if N.Right /= null then 
        Destroy_Tree(N.Right);
     end if;
     Free(N);
  end Destroy_Tree;
  function Tree(Value : Integer; Left : Node_Access; Right : Node_Access) return Node_Access is
     Temp : Node_Access := new Node;
  begin
     Temp.Data := Value;
     Temp.Left := Left;
     Temp.Right := Right;
     return Temp;
  end Tree;
  procedure Preorder(N : Node_Access) is
  begin
     Put(Integer'Image(N.Data));
     if N.Left /= null then
        Preorder(N.Left);
     end if;
     if N.Right /= null then
        Preorder(N.Right);
     end if;
  end Preorder;
  procedure Inorder(N : Node_Access) is
  begin
     if N.Left /= null then
        Inorder(N.Left);
     end if;
     Put(Integer'Image(N.Data));
     if N.Right /= null then
        Inorder(N.Right);
     end if;
  end Inorder;
  procedure Postorder(N : Node_Access) is
  begin
     if N.Left /= null then
        Postorder(N.Left);
     end if;
     if N.Right /= null then
        Postorder(N.Right);
     end if;
     Put(Integer'Image(N.Data));
  end Postorder;
  procedure Levelorder(N : Node_Access) is
     package Queues is new Ada.Containers.Doubly_Linked_Lists(Node_Access);
     use Queues;
     Node_Queue : List;
     Next : Node_Access;
  begin
     Node_Queue.Append(N);
     while not Is_Empty(Node_Queue) loop
        Next := First_Element(Node_Queue);
        Delete_First(Node_Queue);
        Put(Integer'Image(Next.Data));
        if Next.Left /= null then
           Node_Queue.Append(Next.Left);
        end if;
        if Next.Right /= null then
           Node_Queue.Append(Next.Right);
        end if;
     end loop;
  end Levelorder;
  N : Node_Access;

begin

  N := Tree(1, 
     Tree(2,
        Tree(4,
           Tree(7, null, null),
           null),
        Tree(5, null, null)),
     Tree(3,
        Tree(6,
           Tree(8, null, null),
           Tree(9, null, null)),
        null));
        
  Put("preorder:    ");
  Preorder(N);
  New_Line;
  Put("inorder:     ");
  Inorder(N);
  New_Line;
  Put("postorder:   ");
  Postorder(N);
  New_Line;
  Put("level order: ");
  Levelorder(N);
  New_Line;
  Destroy_Tree(N);

end Tree_traversal;</lang>

C

<lang c>#include <stdlib.h>

1. include <stdio.h>

typedef struct node_s {

 int value;
 struct node_s* left;
 struct node_s* right;

} *node;

node tree(int v, node l, node r) {

 node n = malloc(sizeof(struct node_s));
 n->value = v;
 n->left  = l;
 n->right = r;
 return n;

}

void destroy_tree(node n) {

 if (n->left)
   destroy_tree(n->left);
 if (n->right)
   destroy_tree(n->right);
 free(n);

}

void preorder(node n, void (*f)(int)) {

 f(n->value);
 if (n->left)
   preorder(n->left, f);
 if (n->right)
   preorder(n->right, f);

}

void inorder(node n, void (*f)(int)) {

 if (n->left)
   inorder(n->left, f);
 f(n->value);
 if (n->right)
   inorder(n->right, f);

}

void postorder(node n, void (*f)(int)) {

 if (n->left)
   postorder(n->left, f);
 if (n->right)
   postorder(n->right, f);
 f(n->value);

}

/* helper queue for levelorder */ typedef struct qnode_s {

 struct qnode_s* next;
 node value;

} *qnode;

typedef struct { qnode begin, end; } queue;

void enqueue(queue* q, node n) {

 qnode node = malloc(sizeof(struct qnode_s));
 node->value = n;
 node->next = 0;
 if (q->end)
   q->end->next = node;
 else
   q->begin = node;
 q->end = node;

}

node dequeue(queue* q) {

 node tmp = q->begin->value;
 qnode second = q->begin->next;
 free(q->begin);
 q->begin = second;
 if (!q->begin)
   q->end = 0;
 return tmp;

}

int queue_empty(queue* q) {

 return !q->begin;

}

void levelorder(node n, void(*f)(int)) {

 queue nodequeue = {};
 enqueue(&nodequeue, n);
 while (!queue_empty(&nodequeue))
 {
   node next = dequeue(&nodequeue);
   f(next->value);
   if (next->left)
     enqueue(&nodequeue, next->left);
   if (next->right)
     enqueue(&nodequeue, next->right);
 }

}

void print(int n) {

 printf("%d ", n);

}

int main() {

 node n = tree(1,
               tree(2,
                    tree(4,
                         tree(7, 0, 0),
                         0),
                    tree(5, 0, 0)),
               tree(3,
                    tree(6,
                         tree(8, 0, 0),
                         tree(9, 0, 0)),
                    0));

 printf("preorder:    ");
 preorder(n, print);
 printf("\n");

 printf("inorder:     ");
 inorder(n, print);
 printf("\n");

 printf("postorder:   ");
 postorder(n, print);
 printf("\n");

 printf("level-order: ");
 levelorder(n, print);
 printf("\n");

 destroy_tree(n);

 return 0;

}</lang>

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]

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

}

1. 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