Double Order Traversal of a Binary Tree in Java
A Double Order Traversal of a binary tree is a traversal method where each node is visited twice. The sequence involves processing the node, traversing its left subtree, processing the node again, and then traversing its right subtree. It ensures that every node is revisited, allowing operations to be performed at both entry and exit points of the node.
Example:
Input:
![Double Order Traversal of a Binary Tree in Java/>
{C}<!-- /wp:html -->
{C}<!-- wp:paragraph -->
<p><strong>Output:</strong> Double Order Traversal for the given tree is: [1, 2, 3, 3, 2, 4, 4, 1, 5, 5, 6, 6]</p>
{C}<!-- /wp:paragraph -->
{C}<!-- wp:paragraph -->
<p><strong>Explanation: </strong>In a Double Order Traversal of the given binary tree, each node is visited before and after traversing its subtrees, resulting in the sequence: 1, 2, 3, 3, 2, 4, 4, 1, 5, 5, 6, 6.</p>
{C}<!-- /wp:paragraph -->
{C}<!-- wp:heading -->
<h2 class=](https://static.tutorialandexample.com/java/double-order-traversal-of-a-binary-tree-in-java1.png)
Algorithm
Step 1: Create a list result to store the traversal order.
Step 2: If the current node is null, return from the function to stop further processing.
Step 3: Add the value of the current node to the result list to record the first visit.
Step 4: Recursively call the doubleOrderTraversal() function on the left child of the current node to process all nodes in the left subtree.
Step 5: Add the value of the current node to the result list again to record the second visit.
Step 6: Recursively call the doubleOrderTraversal() function on the right child of the current node to process all nodes in the right subtree.
FileName: DoubleOrderTraversalRecursive.java
import java.util.ArrayList; import java.util.List; class TreeNode { int val; TreeNode left, right; TreeNode(int val) { this.val = val; this.left = null; this.right = null; } } public class DoubleOrderTraversalRecursive { public static void main(String[] args) { // Constructing the tree TreeNode root = new TreeNode(1); root.left = new TreeNode(2); root.right = new TreeNode(5); root.left.left = new TreeNode(3); root.left.right = new TreeNode(4); root.right.right = new TreeNode(6); // List to hold the result of traversal Listresult = new ArrayList<>(); // Perform Double Order Traversal doubleOrderTraversal(root, result); // Print the result System.out.println("Double Order Traversal for the given tree is: " + result); } // Recursive function for Double Order Traversal public static void doubleOrderTraversal(TreeNode node, List result) { if (node == null) return; // Base case: if the node is null, return result.add(node.val); // First visit of the node doubleOrderTraversal(node.left, result); // Recur on the left subtree result.add(node.val); // Second visit of the node doubleOrderTraversal(node.right, result); // Recur on the right subtree } }
Output:
Double Order Traversal for the given tree is: [1, 2, 3, 3, 2, 4, 4, 1, 5, 5, 6, 6]
Complexity Analysis:
Time Complexity: O(n), where n is the number of nodes in the tree, as each node is visited exactly twice.
Space Complexity: O(h), where h is the height of the tree, due to the recursive call stack used during traversal.
Iterative Approach
Algorithm
Step 1: Create a stack to manage the nodes to be processed and a list result to store the traversal order.
Step 2: Push the root node onto the stack with a flag indicating it has not been visited yet.
Step 3: Pop a node from the stack and check if it has been visited once.
Step 4: If it has been visited once, add its value to the result list (second visit) and push its right child onto the stack if it exists.
Step 5: If the node has not been visited before, add its value to the result list (first visit).
Step 6: Mark the node as visited once and push it back onto the stack.
Step 7: Push its left child onto the stack if it exists.
Step 8: Repeat the process until the stack is empty, ensuring that each node is visited twice, with the left and right subtrees processed appropriately in between the visits.
FileName: DoubleOrderTraversalIterative.java
import java.util.ArrayList; import java.util.List; import java.util.Stack; class TreeNode { int val; TreeNode left, right; TreeNode(int val) { this.val = val; this.left = null; this.right = null; } } public class DoubleOrderTraversalIterative { // Helper class to manage node visits static class NodeVisit { TreeNode node; boolean visitedOnce; NodeVisit(TreeNode node, boolean visitedOnce) { this.node = node; this.visitedOnce = visitedOnce; } } public static void main(String[] args) { // Constructing the tree TreeNode root = new TreeNode(1); root.left = new TreeNode(2); root.right = new TreeNode(5); root.left.left = new TreeNode(3); root.left.right = new TreeNode(4); root.right.right = new TreeNode(6); // Perform Double Order Traversal Listresult = doubleOrderTraversal(root); // Print the result System.out.println("Double Order Traversal for the given tree is: " + result); } // Iterative function for Double Order Traversal public static List doubleOrderTraversal(TreeNode root) { List result = new ArrayList<>(); if (root == null) return result; // If the tree is empty, return empty list Stack stack = new Stack<>(); stack.push(new NodeVisit(root, false)); // Start with the root node while (!stack.isEmpty()) { NodeVisit current = stack.pop(); if (current.visitedOnce) { result.add(current.node.val); // Second visit of the node if (current.node.right != null) stack.push(new NodeVisit(current.node.right, false)); // Push right child if exists } else { result.add(current.node.val); // First visit of the node stack.push(new NodeVisit(current.node, true)); // Mark the node as visited once if (current.node.left != null) stack.push(new NodeVisit(current.node.left, false)); // Push left child if exists } } return result; } }
Output:
Double Order Traversal for the given tree is: [1, 2, 3, 3, 2, 4, 4, 1, 5, 5, 6, 6]
Complexity Analysis:
Time Complexity: O(n), where n is the number of nodes in the tree, as each node is visited exactly twice.
Space Complexity: O(n), as the stack can hold up to n nodes in the worst case, especially for a skewed tree.