Given a Binary Tree, the task is to find it’s Triple Order Traversal.
Triple Order Traversal is a tree traversal technique in which every node is traversed thrice in the following order:
- Visit the root node
- Traverse the left subtree
- Visit the root node
- Traverse the right subtree
- Visit the root node.
Examples:
Input:
A
/ \
B C
/ \ \
F D E
Output: A B F F F B D D D B A C C E E E C A
Input:
A
/ \
B C
/ \
E D
/
F
Output: A B E F F F E E B D D D B A C C C A
Approach:
Follow the steps below to solve the problem:
- Start the 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.
- Again, print the current node.
- 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 triple// order traversal of a binary tree#include <iostream>using namespace std;// Structure of a Nodestruct node { char data; struct node *left, *right;};// Function to create new nodestruct node* newNode(char ch){ // Allocating a new node in the memory. struct node* Node = new node(); Node->data = ch; Node->left = NULL; Node->right = NULL; return Node;}// Function to print Triple Order traversalvoid tripleOrderTraversal(struct node* root){ if (root) { // Print the current node cout << root->data << " "; // Traverse left subtree tripleOrderTraversal(root->left); // Print the current node cout << root->data << " "; // Traverse right subtree tripleOrderTraversal(root->right); // Print the current node cout << root->data << " "; }}// Driver Codeint main(){ struct node* root = newNode('A'); root->left = newNode('B'); root->right = newNode('C'); root->left->left = newNode('F'); root->left->right = newNode('D'); root->right->right = newNode('E'); tripleOrderTraversal(root);} |
Java
// Java program to implement triple// order traversal of a binary treeimport java.util.*;class GFG{// Structure of a Nodestatic class node{ char data; node left, right;};// Function to create new nodestatic node newNode(char ch){ // Allocating a new node in the memory. node n = new node(); n.data = ch; n.left = null; n.right = null; return n;}// Function to print Triple Order traversalstatic void tripleOrderTraversal(node root){ if (root != null) { // Print the current node System.out.print(root.data + " "); // Traverse left subtree tripleOrderTraversal(root.left); // Print the current node System.out.print(root.data + " "); // Traverse right subtree tripleOrderTraversal(root.right); // Print the current node System.out.print(root.data + " "); }}// Driver Codepublic static void main(String[] args){ node root = newNode('A'); root.left = newNode('B'); root.right = newNode('C'); root.left.left = newNode('F'); root.left.right = newNode('D'); root.right.right = newNode('E'); tripleOrderTraversal(root);}}// This code is contributed by amal kumar choubey |
Python3
# Python3 program to implement triple# order traversal of a binary tree# Structure of nodeclass Node: # Initialise the node def __init__(self, ch): self.data = ch self.left = None self.right = None # Function to print the Triple Order Traversaldef tripleOrderTraversal(root): if root: # Print the current node print(root.data, end = ' ') # Print the left subtree tripleOrderTraversal(root.left) # Print the current node print(root.data, end = ' ') # Print the right subtree tripleOrderTraversal(root.right) # Print the current node print(root.data, end = ' ') # Driver coderoot = Node('A')root.left = Node('B')root.right = Node('C')root.left.left = Node('F')root.left.right = Node('D')root.right.right = Node('E')tripleOrderTraversal(root) # This code is contributed by Stuti Pathak |
C#
// C# program to implement triple// order traversal of a binary treeusing System;class GFG{// Structure of a Nodepublic class node{ public char data; public node left, right;};// Function to create new nodestatic node newNode(char ch){ // Allocating a new node in the memory. node n = new node(); n.data = ch; n.left = null; n.right = null; return n;}// Function to print Triple Order traversalstatic void tripleOrderTraversal(node root){ if (root != null) { // Print the current node Console.Write(root.data + " "); // Traverse left subtree tripleOrderTraversal(root.left); // Print the current node Console.Write(root.data + " "); // Traverse right subtree tripleOrderTraversal(root.right); // Print the current node Console.Write(root.data + " "); }}// Driver Codepublic static void Main(String[] args){ node root = newNode('A'); root.left = newNode('B'); root.right = newNode('C'); root.left.left = newNode('F'); root.left.right = newNode('D'); root.right.right = newNode('E'); tripleOrderTraversal(root);}}// This code is contributed by amal kumar choubey |
Javascript
<script>// javascript Program to implement triple// order traversal of a binary tree// Structure of a Nodeclass node { constructor() { this.data = 0; this.left = null; this.right = null; }};// Function to create new nodefunction newNode(ch){ // Allocating a new node in the memory. var n = new node(); n.data = ch; n.left = null; n.right = null; return n;}// Function to print Triple Order traversalfunction tripleOrderTraversal(root){ if (root) { // Print the current node document.write( root.data + " "); // Traverse left subtree tripleOrderTraversal(root.left); // Print the current node document.write( root.data + " "); // Traverse right subtree tripleOrderTraversal(root.right); // Print the current node document.write( root.data + " "); }}// Driver Codevar root = newNode('A');root.left = newNode('B');root.right = newNode('C');root.left.left = newNode('F');root.left.right = newNode('D');root.right.right = newNode('E');tripleOrderTraversal(root);</script> |
Output:
A B F F F B D D D B A C C E E E C A
Time Complexity: O(N), where N is the total number of nodes in the binary tree.
Auxiliary Space: O(N)
Applications: Euler tour of a tree is a modified version of triple order traversal.
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
