Euler Tour Traversal is a generic traversal of a binary tree. It walks around the tree and visit each node three times:

• on the left, before the Euler tour of the node's left subtree
• from below, as we finish the tour of the left subtree
• on the right, after we finish the Euler tour of the right subtree.

note: if the node is a leaf, we consider the visits to all occur at once

Below is a Euler Tour Traversal implementation in Java. The program will create a Binary Search Tree and then traverse in Euler Tour.

package binaryTree;

import java.util.Scanner;

public class BinarySearchTree {

	private Node root;

	private static class Node {
		Node left;
		Node right;
		int data;

		Node(int newData) {
			left = null;
			right = null;
			data = newData;
		}
	}


	public void insert(int data) {
		root = insert(root, data);
	}

	private Node insert(Node node, int data) {
		if (node == null) {
			node = new Node(data);
		}
		else {
			if (data <= node.data) 
				node.left = insert(node.left, data);
			else
				node.right = insert(node.right, data);
		}
		return(node);
	} 
	

	private void EulerTour(Node node) {
		if (node == null) 
			return;

		System.out.print(node.data + "  ");
		if (node.left != null){
			EulerTour(node.left);
			System.out.print(node.data + "  ");
		}

		if(node.right != null){
			EulerTour(node.right);
			System.out.print(node.data + "  ");
		}			
	}

	
	public static void main(String[] args){
		Scanner input = new Scanner(System.in);
		BinarySearchTree t = new BinarySearchTree();
		
		System.out.print("How many nodes\t:");
		int n = input.nextInt();
		
		for(int i = 1; i <= n; i++){
			System.out.print("Node " + i +":\t");
			t.insert(input.nextInt());
		}
		
		t.EulerTour(t.root);
	}
}