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:
![Flatten binary tree in order of post-order traversal in Java/>
<!-- /wp:html -->
<!-- wp:paragraph -->
<p><strong>Output:</strong> Flattened list in post-order traversal: [3, 4, 2, 6, 5, 1]</p>
<!-- /wp:paragraph -->
<!-- wp:paragraph -->
<p><strong>Explanation: </strong>In the given binary tree, the post-order traversal sequence is [3, 4, 2, 6, 5, 1]. This sequence represents the order in which nodes are visited: first the left subtree (3, 4, 2), then the right subtree (6, 5), and finally the root (1). So, when flattened in post-order traversal, the resulting list is [3, 4, 2, 6, 5, 1].</p>
<!-- /wp:paragraph -->
<!-- wp:heading -->
<h2 class=](https://static.tutorialandexample.com/java/flatten-binary-tree-in-order-of-post-order-traversal-in-java1.png)
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 ListflattenTreeRecursive(TreeNode root) { List result = new ArrayList<>(); flattenHelper(root, result); return result; } private void flattenHelper(TreeNode node, List 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 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 ListflattenTreeIterative(TreeNode root) { List result = new ArrayList<>(); if (root == null) return result; Stack 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 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.