# Mix Order Traversal of a Binary Tree in Java

Mix Order Traversal is a traversal method that combines multiple standard tree traversal techniques such as in-order, pre-order, post-order, and level-order.

Given a Binary Tree consisting of n nodes. The task is to find the mix order traversal.

Example

## Mix Order Traversal using Preorder and Inorder

Preorder Traversal: 1 2 4 5 3 6

Inorder Traversal: 4 2 5 1 3 6

Output: 2 4 5 1 3 6

## Approach 1: Using Inorder-Preorder Mix Traversal

A mixed order traversal of a binary tree using a combination of inorder and preorder traversals.

### Algorithm

Step 1: Define a TreeNode class with properties value, leftChild, and rightChild.

Step 2: Implement a createNode method to initialize a new TreeNode with a given character.

Step 3: Define an inOrderTraversal method:

Step 3.1: Recursively visits the left child using preOrderTraversal.

Step 3.2: Prints the value of the current node.

Step 3.3: Recursively visits the right child using preOrderTraversal.

Step 4: Define a preorderTraversal method that:

Step 4.1: Prints the value of the current node.

Step 4.2: Recursively visits the left child using inOrderTraversal.

Step 4.3: Recursively visits the right child using inOrderTraversal.

Step 5: Construct a binary tree and call inOrderTraversal to start the traversal.

FileName: InorderPreorder.java

```import java.util.*;

public class InorderPreorder {

// TreeNode structure

static class TreeNode {

char value;

TreeNode leftChild, rightChild;

}

// Creates and initializes a new TreeNode

static TreeNode createNode(char character) {

// Allocating memory to a new TreeNode

TreeNode node = new TreeNode();

node.value = character;

node.leftChild = null;

node.rightChild = null;

return node;

}

// Perform Inorder Traversal

static void inOrderTraversal(TreeNode root) {

if (root != null) {

// Visit left subtree using Preorder traversal

preOrderTraversal(root.leftChild);

// Print current node value

System.out.print(root.value + " ");

// Visit right subtree using Preorder traversal

preOrderTraversal(root.rightChild);

}

}

// Perform Preorder Traversal

static void preOrderTraversal(TreeNode root) {

if (root != null) {

// Print current node value

System.out.print(root.value + " ");

// Visit left subtree using Inorder traversal

inOrderTraversal(root.leftChild);

// Visit right subtree using Inorder traversal

inOrderTraversal(root.rightChild);

}

}

public static void main(String[] args) {

// Create root of the tree

TreeNode rootNode = createNode('1');

// Create left subtree

rootNode.leftChild = createNode('2');

rootNode.leftChild.leftChild = createNode('4');

rootNode.leftChild.rightChild = createNode('5');

// Create right subtree

rootNode.rightChild = createNode('3');

rootNode.rightChild.leftChild = createNode('6');

// Perform Mix order traversal starting from root

inOrderTraversal(rootNode);

}

}```

Output

`2 4 5 1 3 6`

Time Complexity: The time complexity of this mixed order traversal is O(n), where n is the number of nodes in the binary tree. Each node is visited once, and the operations performed at each node (printing the value and making recursive calls) are constant-time operations.

Space Complexity: The space complexity is O(h), where h is the height of the tree. This complexity arises from the recursive calls, which require stack space proportional to the height of the tree.

## Approach 2: Preorder – Postorder Mix Traversal

A mixed traversal approach that combines elements of preorder and postorder traversals. This method involves traversing the tree by first visiting nodes in preorder fashion (root, left, right) and then postorder fashion (left, right, root). This approach prints nodes in a sequence that uniquely integrates both traversal methods.

### Algorithm

Step 1: Define a TreeNode class with properties value, leftChild, and rightChild.

Step 2:  Implement a createNode method to initialize a new TreeNode with a given character.

Step 3: Preorder Traversal:

Step 3.1: If the current node is not null:

Step 3.2: Print the value of the current node.

Step 3.3: Recursively visit the left subtree using postOrderTraversal.

Step 3.4: Recursively visit the right subtree using postOrderTraversal.

Step 4: Postorder Traversal:

Step 4.1: If the current node is not null:

Step 4.2: Recursively visit the left subtree using preOrderTraversal.

Step 4.3: Recursively visit the right subtree using preOrderTraversal.

Step 4.4: Print the value of the current node.

Step 5: Construct a binary tree by creating nodes and linking them appropriately.

Step 6: Initiate the mixed order traversal starting from the root node using preOrderTraversal.

FileName: PreorderPostorder.java

```public class PreorderPostorder {

// TreeNode structure

static class TreeNode {

char value;

TreeNode leftChild, rightChild;

}

// Creates and initializes a new TreeNode

static TreeNode createNode(char character) {

// Allocating memory to a new TreeNode

TreeNode node = new TreeNode();

node.value = character;

node.leftChild = null;

node.rightChild = null;

return node;

}

// Perform Preorder Traversal

static void preOrderTraversal(TreeNode root) {

if (root != null) {

// Print the current node value

System.out.print(root.value + " ");

// Recursively visit the left subtree using Postorder traversal

postOrderTraversal(root.leftChild);

// Recursively visit the right subtree using Postorder traversal

postOrderTraversal(root.rightChild);

}

}

// Perform Postorder Traversal

static void postOrderTraversal(TreeNode root) {

if (root != null) {

// Recursively visit the left subtree using Preorder traversal

preOrderTraversal(root.leftChild);

// Recursively visit the right subtree using Preorder traversal

preOrderTraversal(root.rightChild);

// Print the current node value

System.out.print(root.value + " ");

}

}

public static void main (String[] args) {

// Create root of the tree

TreeNode root = createNode('1');

// Create left subtree

root.leftChild = createNode('2');

root.leftChild.leftChild = createNode('6');

root.leftChild.rightChild = createNode('4');

// Create right subtree

root.rightChild = createNode('3');

root.rightChild.rightChild = createNode('5');

// Starting Mix order traversal

preOrderTraversal(root);

}

}```

Output

`1 6 4 2 5 3`

Time Complexity: The time complexity of this mixed traversal is O(n), where n is the number of nodes in the binary tree. Each node is visited once during the traversal, and the operations performed at each node (printing the value and making recursive calls) are constant-time operations.

Space Complexity: The space complexity is O(h), where h is the height of the binary tree. This complexity arises from the recursive calls, which require stack space proportional to the height of the tree.

## Approach 3: Using Inorder – Postoder Mix Traversal

A mixed traversal approach that integrates elements of inorder and postorder traversals. This method involves traversing the binary tree by first visiting nodes in postorder fashion (left, right, root) and then inorder fashion (left, root, right). This approach prints nodes in a sequence that uniquely integrates both traversal methods.

### Algorithm

Step 1: Define a TreeNode class with properties value, leftChild, and rightChild.

Step 2: Implement a createNode method to initialize a new TreeNode with a given character.

Step 3: Inorder Traversal:

Step 3.1: If the current node is not null:

Step 3.2: Recursively visit the left subtree using postOrderTraversal.

Step 3.3: Print the value of the current node.

Step 3.4: Recursively visit the right subtree using postOrderTraversal.

Step 4: Postorder Traversal:

Step 4.1: If the current node is not null:

Step 4.2: Recursively visit the left subtree using inOrderTraversal.

Step 4.3: Recursively visit the right subtree using inOrderTraversal.

Step 4.4: Print the value of the current node.

Step 5: Initiate the mixed order traversal starting from the root node using inOrderTraversal.

FileName: InorderPostorder.java

```import java.util.*;

public class InorderPostorder {

// TreeNode structure

static class TreeNode {

char value; // The value of the node

TreeNode leftChild; // The left child of the node

TreeNode rightChild; // The right child of the node

}

// Creates and initializes a new TreeNode

static TreeNode createNode(char character) {

// Allocating memory to a new TreeNode

TreeNode newNode = new TreeNode();

newNode.value = character; // Set the value of the node

newNode.leftChild = null; // Initialize the left child as null

newNode.rightChild = null; // Initialize the right child as null

return newNode;

}

// Perform Inorder Traversal (but actually performing postorder traversal)

static void inOrderTraversal(TreeNode root) {

if (root != null) {

postOrderTraversal(root.leftChild); // Traverse the left subtree

System.out.print(root.value + " "); // Print the value of the current node

postOrderTraversal(root.rightChild); // Traverse the right subtree

}

}

// Perform Postorder Traversal (but actually performing inorder traversal)

static void postOrderTraversal(TreeNode root) {

if (root != null) {

inOrderTraversal(root.leftChild); // Traverse the left subtree

inOrderTraversal(root.rightChild); // Traverse the right subtree

System.out.print(root.value + " "); // Print the value of the current node

}

}

public static void main (String[] args) {

// Given tree

TreeNode rootNode = createNode('1'); // Create the root node with value '1'

rootNode.leftChild = createNode('2'); // Create the left child of the root node with value '2'

rootNode.rightChild = createNode('3'); // Create the right child of the root node with value '3'

rootNode.leftChild.leftChild = createNode('4'); // Create the left child of the left child of the root node with value '4'

rootNode.leftChild.rightChild = createNode('5'); // Create the right child of the left child of the root node with value '5'

rootNode.rightChild.rightChild = createNode('6'); // Create the right child of the right child of the root node with value '6'

// Starting Mix order traversal

inOrderTraversal(rootNode); // Start the traversal from the root node

}

}```

Output

`4 5 2 1 6 3`

Time Complexity: The time complexity of this mixed traversal is O(n), where n is the number of nodes in the tree. Each node is visited once during the traversal, and the operations performed at each node (printing the value and making recursive calls) are constant-time operations.

Space Complexity: The space complexity is O(h), where h is the height of the binary tree. This complexity arises from the recursive calls, which require stack space proportional to the height of the tree.