Binary Tree Postorder Traversal Editorial

Practice Problem Link: Binary Tree Postorder Traversal

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given a binary tree, return the postorder traversal of its elements.

Approach

To get the postorder traversal of a binary tree first visit the left subtree, then the right subtree followed by the current root for each node recursively.

Analysis

• Time Complexity: O(n)
• Auxiliary Space Complexity: O(1)

Implementation

C++

/* This is the Node class definition

class Node {
public:
    Node* left;
    Node* right;
    int data;

    Node(int data) {
        this->left = NULL;
        this->right = NULL;
        this->data = data;
    }
};
*/
void getPostorderTraversalUtil(Node* root, vector<int> &traversal) {
	if (root == NULL) {
		return;
	}
	getPostorderTraversalUtil(root->left, traversal);
	getPostorderTraversalUtil(root->right, traversal);
	traversal.push_back(root->data);
}

vector<int> getPostorderTraversal(Node* root) {
	vector<int> traversal;
	getPostorderTraversalUtil(root, traversal);
	return traversal;
}

Java

/* This is the Node class definition

class Node {
	public Node left;
    public Node right;
    int data;

    Node(int data) {
        this.data = data;
    }
}
*/

class Solution {
	void getPostorderTraversalUtil(Node root, List<Integer> traversal) {
		if (root == null) {
			return;
		}
		
		getPostorderTraversalUtil(root.left, traversal);
		getPostorderTraversalUtil(root.right, traversal);
		traversal.add(root.data);
	}
	List<Integer> getPostorderTraversal(Node root) {
		List<Integer> traversal = new ArrayList<Integer>();
		getPostorderTraversalUtil(root, traversal);
		return traversal;
	}
}