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.
// 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]
Write a recursive definition for post-order traversal of a binary tree, including the base case and the recursive step.
The base case is the same one as in the previous two problems:
Base Case: Return from the function if node is null.
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.
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.
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.
Your questions are private and won't be used to evaluate your performance.
Your questions are private and won't be used to evaluate your performance.