Posted on by Kalkicode
Code Binary Tree

# Euler tour of Binary Tree

In this article, we will explore the concept of the Euler tour of a binary tree. The Euler tour is a way to traverse a binary tree and represent it in a specific sequence. We will provide a Java program that demonstrates how to perform an Euler tour of a binary tree and print the resulting sequence.

## Problem Statement

Given a binary tree, we want to perform an Euler tour of the tree and print the sequence of nodes visited during the tour. The Euler tour includes visiting each node in the tree exactly three times: first when entering its subtree, second when exiting its left subtree, and third when exiting its right subtree.

## Example

Let's consider a binary tree as an example:

``````
9
/ \
5   7
/ \   \
1   6   11
/   / \   \
10  4   8   20
/ \
2   3
``````

The Euler tour of this tree, along with the sequence of node values visited, is as follows:

``9 5 1 10 1 5 6 4 6 8 2 8 3 8 6 5 9 7 11 20 11 7 9``

In this sequence, each node is visited three times, satisfying the Euler tour properties.

## Idea to Solve the Problem

To perform an Euler tour of a binary tree, we can use a recursive approach. We will create a function that traverses the tree in a specific order, visiting each node three times as required by the Euler tour definition. We will also keep track of the parent node to print it when exiting a subtree.

## Pseudocode

Here is the pseudocode for performing an Euler tour of a binary tree:

``````function eulerPath(node, parent):
if node is null:
return
print node.data // Visit node when entering its subtree
eulerPath(node.left, node) // Visit left subtree
print node.data // Visit node when exiting its left subtree
eulerPath(node.right, node) // Visit right subtree
print node.data // Visit node when exiting its right subtree
if parent is not null:
print parent.data // Print parent when exiting node's subtree

function main():
Create a binary tree
Build the binary tree with nodes and edges
Call eulerPath(root, null) to perform Euler tour and print sequence

main()``````

## Algorithm Explanation

1. Create a function `eulerPath(node, parent)` to perform the Euler tour.
2. If the current node `node` is null, return.
3. Print the data of the current node `node` when entering its subtree.
4. Recursively call `eulerPath` on the left subtree to visit the left subtree.
5. Print the data of the current node `node` when exiting its left subtree.
6. Recursively call `eulerPath` on the right subtree to visit the right subtree.
7. Print the data of the current node `node` when exiting its right subtree.
8. If the `parent` is not null, print the data of the parent node when exiting the current node's subtree.
9. In the `main` function, create a binary tree, build it with nodes and edges, and call `eulerPath(root, null)` to perform the Euler tour and print the sequence.

## Time Complexity of the Code

The time complexity of this code is O(N), where N is the number of nodes in the binary tree. This is because we visit each node exactly three times during the Euler tour, and the Euler tour takes linear time with respect to the number of nodes.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post