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.

Code Solution

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.

New Comment