Practice: Binary Tree Postorder Traversal
In this assignment, your task is to solve the "Postorder Traversal" problem with our final DFS pattern. Try solving the problem on your own using recursion.
Problem Description
// Given the root node of a binary tree, implement a
// function `postorderTraversal` that returns an
// array containing the values of the nodes visited in
// a postorder traversal.
class Node {
constructor(value) {
this.val = value;
this.left = null;
this.right = null;
}
}
// Helper function for test cases
function buildTree(arr) {
if (arr.length === 0) {
return null;
}
const nodes = [];
const val = arr.shift();
const root = new Node(val);
nodes.push(root);
while (arr.length > 0) {
const curr = nodes.shift();
const leftVal = arr.shift();
if (leftVal !== null) {
curr.left = new Node(leftVal);
nodes.push(curr.left);
}
if (arr.length > 0) {
const rightVal = arr.shift();
if (rightVal !== null) {
curr.right = new Node(rightVal);
nodes.push(curr.right);
}
}
}
return root;
}
// Test cases
const tree1 = buildTree([1, null, 2, 3]);
console.log(postorderTraversal(tree1)); // Output: [3, 2, 1]
const tree2 = buildTree([1, 2, 3, null, null, 4, null, null, 5]);
console.log(postorderTraversal(tree2)); // Output: [2, 5, 4, 3, 1]
const tree3 = buildTree([5, 3, null, 2, null, 1, null]);
console.log(postorderTraversal(tree3)); // Output: [1, 2, 3, 5]
const tree4 = buildTree([10, 5, 15, null, 6, 12, 21, null, null, 11]);
console.log(postorderTraversal(tree4)); // Output: [6, 5, 11, 12, 21, 15, 10]
Exercises
Write a recursive definition for post-order traversal of a binary tree, including the base case and the recursive step.
View Our Solution Work in Code Editor
Base Case
The base case is the same one as in the previous two problems:
Base Case: Return from the function if node is null.
Recursive Definition
For the recursive definition in this problem, like in the previous problem, we have to follow a pattern, this time LRN.
Recursive Definition: Perform a postorder traversal by first traversing current node's left child, then perform a postorder traversal on the current node's right child, and finally, add the node's value to the result array.
Now implement the post-order traversal.
View Our Solution Work in Code Editor
function postorderTraversal(root) {
const result = [];
function traverse(node) {
if (node === null) {
return;
}
traverse(node.left);
traverse(node.right);
result.push(node.val);
}
traverse(root);
return result;
}
Identify the time and space complexity of your post-order traversal.
View Our Solution Work in Code Editor
Time Complexity: O(N), where N is the number of nodes in the tree. Again, we need to visit each node exactly once.
Space Complexity: O(h) for the recursive implementation due to the call stack, where h is the tree's height.