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.