# Flatten binary tree in order of post-order traversal in Java

Flattening a binary tree in the order of post-order traversal in Java means rearranging the tree nodes such that all the nodes are visited in post-order sequence, and the resulting structure is flattened into a list or an array. Post-order traversal visits the left subtree, then the right subtree, and finally the root node.

Example:

Input:

Recursive Approach

### Algorithm

Step 1: Recursively traverse the left subtree.

Step 2: Recursively traverse the right subtree.

Step 3: Visit the current node, adding its value to the result.

Step 4: After traversing both subtrees, set the left child of the current node to null and the right child to the previously visited node.

FileName: BinaryTreeFlattening.java

`import java.util.*;class TreeNode {    int val;    TreeNode left, right;    public TreeNode(int val) {        this.val = val;    }}public class BinaryTreeFlattening {     // Recursive approach    public List<Integer> flattenTreeRecursive(TreeNode root) {        List<Integer> result = new ArrayList<>();        flattenHelper(root, result);        return result;    }    private void flattenHelper(TreeNode node, List<Integer> result) {        if (node == null) return;        // Traverse left subtree        flattenHelper(node.left, result);        // Traverse right subtree        flattenHelper(node.right, result);        // Add current node's value to result        result.add(node.val);    }    // Helper function to create binary tree from the given example input    public TreeNode createExampleTree() {        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);        return root;    }    // Main method to test the Recursive approach    public static void main(String[] args) {        BinaryTreeFlattening solution = new BinaryTreeFlattening();        TreeNode root = solution.createExampleTree();        // Using Recursive approach        List<Integer> resultRecursive = solution.flattenTreeRecursive(root);        System.out.println("Flattened list in post-order traversal: " + resultRecursive);    }}`

Output:

`Flattened list in post-order traversal: [3, 4, 2, 6, 5, 1]`

Complexity Analysis: The time complexity of the code is O(n), where n is the number of nodes in the tree, as each node is visited once. The space complexity is O(1) if the flattening is performed in place, or O(n) if additional space is required to store the result.

## Iterative Approach Using Stack

### Algorithm

Step 1: Initialize an empty stack for iterative traversal.

Step 2: Push the root node onto the stack.

Step 3: While the stack is not empty, pop a node, add its value to the front of the result list, and push its right and left children onto the stack.

Step 4: Return the result list containing flattened tree nodes in reverse post-order traversal.

FileName: BinaryTreeFlattening1.java

`import java.util.*;class TreeNode {    int val;    TreeNode left, right;    public TreeNode(int val) {        this.val = val;    }}public class BinaryTreeFlattening1 {    // Iterative approach using stack    public List<Integer> flattenTreeIterative(TreeNode root) {        List<Integer> result = new ArrayList<>();        if (root == null) return result;        Stack<TreeNode> stack = new Stack<>();        stack.push(root);        while (!stack.isEmpty()) {            TreeNode current = stack.pop();            result.add(0, current.val); // Add node value to the front of the list (reverse post-order)                       // Push right child first, then left child            if (current.left != null) stack.push(current.left);            if (current.right != null) stack.push(current.right);        }        return result;    }    // Helper function to create binary tree from the given example input    public TreeNode createExampleTree() {        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);        return root;    }    // Main method to test the Iterative approach    public static void main(String[] args) {        BinaryTreeFlattening1 solution = new BinaryTreeFlattening1();        TreeNode root = solution.createExampleTree();        // Using Iterative approach        List<Integer> resultIterative = solution.flattenTreeIterative(root);        System.out.println("Flattened list in post-order traversal: " + resultIterative);    }}`

Output:

`Flattened list in post-order traversal: [3, 4, 2, 6, 5, 1]`

Complexity Analysis: The time complexity of the code is O(n), where n is the number of nodes in the binary tree, as each node is visited once. The space complexity is also O(n) due to the stack used for traversal, potentially storing all nodes in the worst case scenario.