1.
Introduction
2.
Problem Statement
3.
Approach
4.
4.1.
What do you mean by a binary tree?
4.2.
How to traverse a binary tree?
5.
Conclusion
Last Updated: Mar 27, 2024

# Double Order Traversal of a Binary Tree

Nishant Rana
1 upvote
Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

## Introduction

Trees play a vital role in our competitive programming for technical rounds at product companies. A binary tree is a non-linear data structure where each node has two children at most named as left and right children.

Double-order traversal means each node in the tree is traversed twice in a particular order.

The order is:

• Visit the node
• Traverse left subtree
• Visit the node
• Traverse right subtree

## Problem Statement

We are given an N nodes binary tree in which our task is to print the Double Order Traversal.

Example:

Input

Output

1 2 4 4 2 5 5 1 3 3  6 6

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

## Approach

We will follow the in-order traversal recursively on the binary tree for double-order traversal.

Steps to be followed to print the Double Order Traversal:

Start the Inorder traversal from the root.

Print the current node’s value.

Recursively call for the left subtree.

Print the current node again.

Recursively call for the right subtree.

After performing the above steps, the Double order Traversal of the Binary Tree will get printed.

Implementation

``````class Solution {

// Node
static class node
{
char data;
node left, right;
};

// Function to create new node
static node newNode(char c)
{

node n =  new node();
n.data = c;
n.left =  null;
n.right =  null;
return n;
}

// Function to print Double Order traversal
static void doubleOrder(node root)
{
if (root ==  null)
return;

// Print Node Value
System.out.print(root.data +  " ");

// Traverse Left Subtree
doubleOrder(root.left);

// Print Node Value
System.out.print(root.data +  " ");

// Traverse Right SubTree
doubleOrder(root.right);
}

// Main  function
public static void main(String[] args)
{
node root = newNode('1');
root.left = newNode('2');
root.right = newNode('3');
root.left.left = newNode('4');
root.left.right = newNode('5');
root.right.right = newNode('6');

doubleOrder(root);
}
}``````

Output

1 2 4 4 2 5 5 1 3 3 6 6

Time Complexity: The time complexity of the above approach is O(N) because we are doing the in-order traversal of the Tree.

Space Complexity: The space complexity of the above approach is O(1) because we are not using any auxiliary space.

Check out this problem - Mirror A Binary Tree

### What do you mean by a binary tree?

It is a non-linear data structure with nodes as elements connected in a tree-like structure where each node should have two children.

### How to traverse a binary tree?

The tree could be traversed using Inorder, Preorder, and Postorder tree traversals.

## Conclusion

• What precisely a binary tree is.
• Meaning of the double order traversal in a binary tree.
• Implementation of double-order binary tree traversal.

Don't stop here; prepare the topic trees in-depth for product-based companies' technical rounds.

Also, don’t forget to practice the wide variety of DSA problems frequently asked in interview rounds readily available on Coding Ninjas Studio