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 of a Binary Tree in Java](https://static.tutorialandexample.com/java/mix-order-traversal-of-a-binary-tree-in-java1.png)
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.