In this assignment, your task is to solve the "Preorder Traversal" problem. As mentioned in the previous assignment, you can implement Depth-First Search (DFS) traversals using either recursion or a stack. The recursive solution is easier to implement, so we'll focus on that.
Our Core Curriculum covers the iterative approach using a stack for all three Depth-First Search traversals in detail.
// Given the root node of a binary tree, implement a
// function `preorderTraversal` that returns an
// array containing the values of the nodes visited in
// a preorder 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(preorderTraversal(tree1)); // Output: [1, 2, 3]
const tree2 = buildTree([1, 2, 3, null, null, 4, null, null, 5]);
console.log(preorderTraversal(tree2)); // Output: [1, 2, 3, 4, 5]
const tree3 = buildTree([5, 3, null, 2, null, 1, null]);
console.log(preorderTraversal(tree3)); // Output: [5, 3, 2, 1]
const tree4 = buildTree([10, 5, 15, null, 6, 12, 21, null, null, 11]);
console.log(preorderTraversal(tree4)); // Output: [10, 5, 6, 15, 12, 11, 21]
Write a recursive definition for pre-order traversal of a binary tree, including the base case and the recursive step.
Let's start with the base case. As in the previous problems, the base case occurs when the node is null. In this scenario, we simply return from the function to prevent accessing the val property of null, which would raise an error.
Base Case: Return from the function if the node is null.
In this case, we don't have to follow a template; instead, we can follow the NLR pattern we learned in the previous assignment. We first want to process the node, then go left, and then go right. When we say go left, we mean we want to perform the preorder traversal on the left child, which means calling the function recursively and passing the left child to it. When we say go right, we mean we want to perform the preorder traversal on the right child, which means calling the function recursively and passing the right child to it.
Recursive Definition: Add the node's value to the result array, then perform a preorder traversal by recursively calling the function on the current node's left child, followed by recursively calling the function on current node's right child.
Now implement the pre-order traversal.
function preorderTraversal(root) {
const result = [];
function traverse(node) {
if (node === null) {
return;
}
result.push(node.val);
traverse(node.left);
traverse(node.right);
}
traverse(root);
return result;
}
Identify the time and space complexity of your pre-order traversal.
Time Complexity: O(N), where N is the number of nodes in the tree. This is because 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.