Sponsored
Sponsored
The simplest way to perform a postorder traversal of a binary tree is recursively. In postorder traversal, you need to traverse the left subtree, then traverse the right subtree, finally visit the root node. This means visiting the left child, then the right child, and then the node itself for each node in the tree.
Time Complexity: O(n), where n is the number of nodes in the binary tree, because each node is visited once.
Space Complexity: O(h), where h is the height of the tree, due to recursive call stack usage.
1#include <stdio.h>
2#include <stdlib.h>
3
4struct TreeNode {
5 int val;
6 struct TreeNode *left;
7 struct TreeNode *right;
8};
9
10void postorderHelper(struct TreeNode* root, int* result, int* returnSize) {
11 if (root == NULL) return;
12 postorderHelper(root->left, result, returnSize);
13 postorderHelper(root->right, result, returnSize);
14 result[(*returnSize)++] = root->val;
15}
16
17int* postorderTraversal(struct TreeNode* root, int* returnSize){
18 *returnSize = 0;
19 int* result = (int*)malloc(100 * sizeof(int));
20 postorderHelper(root, result, returnSize);
21 return result;
22}This C solution uses a helper function, postorderHelper, to perform the traversal recursively. It first processes the left child, then the right child, and finally the root node, appending each value to the result array. This order ensures a postorder traversal, which visits each node in the left-right-root order.
To perform postorder traversal iteratively, two stacks can be used. The first stack is used to perform a modified preorder traversal (root-right-left), while the second stack reverses this order to provide the postorder traversal (left-right-root). This approach allows the sequence of visiting nodes in postorder traversal without recursion.
Time Complexity: O(n) where n is the number of nodes.
Space Complexity: O(n) due to the usage of two stacks, each containing n nodes in the worst case for balanced or full trees.
This JavaScript solution circumvents recursion by employing two stacks to process the tree. The initial stack (stack1) uses root-right-left sequence collecting nodes, which are subsequently popped from stack2 in reversed order to deliver a left-right-root traversal sequence.