Iterative Postorder Traversal (1 Stack)
Learning Traversals DSA practice problem on Onlearn.
Difficulty: medium.
Topics: Recursive Postorder Traversal of a Binary Tree, Binary Tree, Tree Traversal, Postorder Traversal, Recursion, complexity analysis, dfs, binary tree, call stack, recursion base case, postorder traversal, recursion, tree traversal, Time & Space Complexity Analysis.
Problem Statement Given the root of a binary tree, return the Postorder Traversal of its nodes' values. In a Postorder traversal, the nodes are recursively visited in the following order: 1. Traverse the Left subtree. 2. Traverse the Right subtree. 3. Visit the Root node. Input Specification The input consists of the root node of a binary tree. The tree structure is represented in the sample test cases as an array where null represents an empty node (level order representation). Output Specification Return a list or array of integers containing the postorder traversal of the tree. Constraints The number of nodes in the tree is in the range [0, 10^5]. 10^9 ≤ Node.val ≤ 10^9 Sample Test Cases Sample Input 1 Sample Output 1 Explanation: 1. Traverse left of 1: (Empty) 2. Traverse right of 1: Subtree rooted at 2 Traverse left of 2: Node 3 Traverse right of 2: (Empty) Visit Root 2 Sequence so far: 3, 2 3. Visit Root 1 Final Sequence: 3, 2, 1 Sample Input 2 Sample Output 2 Explanation: 1. Left Subtree (Root 2): Postorder is 4, 5, 2 2. Right Subtree (Root 3): Postorder is 3 3. Root: 1 Final Sequence: 4 5 2 3 1 Sample Input 3 Sample Output 3 Difficulty Level Medium