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>

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 = Node { value :: a,

                    left  :: Maybe (Tree a),
                    right :: Maybe (Tree a) }

preorder :: Tree a -> [a] preorder (Node v l r) =

   [v] ++
   maybe [] preorder l ++
   maybe [] preorder r

inorder :: Tree a -> [a] inorder (Node v l r) =

   maybe [] inorder l ++
   [v] ++
   maybe [] inorder r

postorder :: Tree a -> [a] postorder (Node v l r) =

   maybe [] postorder l ++
   maybe [] postorder r ++
   [v]

levelorder :: Tree a -> [a] levelorder x = loop [x]

   where loop [] = []
         loop (Node v l r : xs) =
             v : loop (xs ++ [x | Just x <- [l,r]])

tree :: Tree Int tree = Node 1

           (Just $ Node 2
                        (Just $ Node 4
                                     (Just $ Node 7 Nothing Nothing)
                                     Nothing)
                        (Just $ Node 5 Nothing Nothing))
           (Just $ Node 3
                        (Just $ Node 6
                                     (Just $ Node 8 Nothing Nothing)
                                     (Just $ Node 9 Nothing Nothing))
                        Nothing)

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 

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