Double Order Traversal of a Binary Tree
Given a Binary Tree consisting of N nodes, the task is to print its Double Order Traversal.
Double Order Traversal is a tree traversal technique in which every node is traversed twice in the following order:
- Visit the Node.
- Traverse the Left Subtree.
- Visit the Node.
- Traverse the Right Subtree.
Examples:
Input:
1
/ \
7 3
/ \ /
4 5 6
Output: 1 7 4 4 7 5 5 1 3 6 6 3
Input:
1
/ \
7 3
/ \ \
4 5 6
Output: 1 7 4 4 7 5 5 1 3 3 6 6
Approach:
The idea is to perform Inorder Traversal recursively on the given Binary Tree and print the node value on visiting a vertex and after the recursive call to the left subtree during the traversal.
Follow the steps below to solve the problem:
- Start Inorder traversal from the root.
- If the current node does not exist, simply return from it.
- Otherwise:
- Print the value of the current node.
- Recursively traverse the left subtree.
- Again, print the current node.
- Recursively traverse the right subtree.
- Repeat the above steps until all nodes in the tree are visited.
Below is the implementation of the above approach:
C++
// C++ Program to implement// the above approach#include <iostream>using namespace std;// Node Structurestruct node { char data; struct node *left, *right;};// Function to create new nodestruct node* newNode(char ch){ // Allocate a new node in memory struct node* Node = new node(); Node->data = ch; Node->left = NULL; Node->right = NULL; return Node;}// Function to print Double Order traversalvoid doubleOrderTraversal(struct node* root){ if (!root) return; // Print Node Value cout << root->data << " "; // Traverse Left Subtree doubleOrderTraversal(root->left); // Print Node Value cout << root->data << " "; // Traverse Right SubTree doubleOrderTraversal(root->right);}// Driver Codeint main(){ struct node* root = newNode('1'); root->left = newNode('7'); root->right = newNode('3'); root->left->left = newNode('4'); root->left->right = newNode('5'); root->right->right = newNode('6'); doubleOrderTraversal(root); return 0;} |
Java
// Java program to implement// the above approachclass GFG{// Node Structurestatic class node { char data; node left, right;};// Function to create new nodestatic node newNode(char ch){ // Allocate a new node in memory node n = new node(); n.data = ch; n.left = null; n.right = null; return n;}// Function to print Double Order traversalstatic void doubleOrderTraversal(node root){ if (root == null) return; // Print Node Value System.out.print(root.data + " "); // Traverse Left Subtree doubleOrderTraversal(root.left); // Print Node Value System.out.print(root.data + " "); // Traverse Right SubTree doubleOrderTraversal(root.right);}// Driver Codepublic static void main(String[] args){ node root = newNode('1'); root.left = newNode('7'); root.right = newNode('3'); root.left.left = newNode('4'); root.left.right = newNode('5'); root.right.right = newNode('6'); doubleOrderTraversal(root);}}// This code is contributed by gauravrajput1 |
Python3
# Python3 program to implement# the above approach# Node Structureclass Node: # Initialise new node def __init__(self, ch): self.data = ch self.left = None self.right = None# Function to print Double Order traversaldef doubleOrderTraveersal(root): if not root: return # Print node value print(root.data, end = " ") # Traverse left subtree doubleOrderTraveersal(root.left) # Print node value print(root.data, end = " ") # Traverse right subtree doubleOrderTraveersal(root.right)# Driver codeif __name__ == '__main__': root = Node(1) root.left = Node(7) root.right = Node(3) root.left.left = Node(4) root.left.right = Node(5) root.right.right = Node(6) doubleOrderTraveersal(root)# This code is contributed by Shivam Singh |
C#
// C# program to implement// the above approachusing System;class GFG{// Node Structureclass node { public char data; public node left, right;};// Function to create new nodestatic node newNode(char ch){ // Allocate a new node in memory node n = new node(); n.data = ch; n.left = null; n.right = null; return n;}// Function to print Double Order traversalstatic void doubleOrderTraversal(node root){ if (root == null) return; // Print Node Value Console.Write(root.data + " "); // Traverse Left Subtree doubleOrderTraversal(root.left); // Print Node Value Console.Write(root.data + " "); // Traverse Right SubTree doubleOrderTraversal(root.right);}// Driver Codepublic static void Main(String[] args){ node root = newNode('1'); root.left = newNode('7'); root.right = newNode('3'); root.left.left = newNode('4'); root.left.right = newNode('5'); root.right.right = newNode('6'); doubleOrderTraversal(root);}}// This code is contributed by gauravrajput1 |
Javascript
<script>// Javascript program to implement// the above approach// Node Structureclass node { constructor() { this.data = 0; this.left = null; this.right = null; }};// Function to create new nodefunction newNode(ch){ // Allocate a new node in memory var n = new node(); n.data = ch; n.left = null; n.right = null; return n;}// Function to print Double Order traversalfunction doubleOrderTraversal(root){ if (root == null) return; // Print Node Value document.write(root.data + " "); // Traverse Left Subtree doubleOrderTraversal(root.left); // Print Node Value document.write(root.data + " "); // Traverse Right SubTree doubleOrderTraversal(root.right);}// Driver Codevar root = newNode('1');root.left = newNode('7');root.right = newNode('3');root.left.left = newNode('4');root.left.right = newNode('5');root.right.right = newNode('6');doubleOrderTraversal(root);</script> |
Output:
1 7 4 4 7 5 5 1 3 3 6 6
Time Complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
