Table of contents
1.
Introduction
2.
Problem Statement
3.
Approach
4.
Frequently Asked Questions
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

Author NISHANT RANA
1 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

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.

 

Binary Tree

 

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

 

Tree

 

Output

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

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);
	}
}
You can also try this code with Online Java Compiler
Run Code

 

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

Frequently Asked Questions

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

In this article, we have covered the following things:

  • 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

Recommended Reading:

Recommended problems -

 

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Happy coding!!

Live masterclass