# 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:

Recursive Approach

### 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        List<Integer> result = 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<Integer> 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        List<Integer> result = 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<Integer> doubleOrderTraversal(TreeNode root) {        List<Integer> result = new ArrayList<>();        if (root == null) return result; // If the tree is empty, return empty list        Stack<NodeVisit> 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.