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

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>

1. include <stdlib.h>
2. 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>

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){
       System.out.print(n.data + " ");
       if(n.getLeft()!= null){
           preorder(n.getLeft());
       }
       if(n.getRight()!= null){
           preorder(n.getRight());
       }
   }
   
   public static void inorder(Node<?> n){
       if(n.getLeft()!= null){
           inorder(n.getLeft());
       }
       System.out.print(n.data + " ");
       if(n.getRight()!= null){
           inorder(n.getRight());
       }
   }
   
   public static void postorder(Node<?> n){
       if(n.getLeft()!= null){
           postorder(n.getLeft());
       }
       if(n.getRight()!= null){
           postorder(n.getRight());
       }
       System.out.print(n.data + " ");
   }
   
   public static void levelorder(Node<?> n) {
       Queue<Node<?>> nodequeue = new LinkedList<Node<?>>();
       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 

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(&block)
   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