Practice: Binary Tree Inorder Traversal
In this assignment, your task is to solve the "Inorder Traversal" problem. Try solving the problem independently, and as always, you can check the walkthrough if needed.
Problem Description
// Given the root node of a binary tree, implement a
// function `inorderTraversal` that returns an
// array containing the values of the nodes visited in
// an inorder 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(inorderTraversal(tree1)); // Output: [1, 3, 2]
const tree2 = buildTree([1, 2, 3, null, null, 4, null, null, 5]);
console.log(inorderTraversal(tree2)); // Output: [2, 1, 4, 5, 3]
const tree3 = buildTree([5, 3, null, 2, null, 1, null]);
console.log(inorderTraversal(tree3)); // Output: [1, 2, 3, 5]
const tree4 = buildTree([10, 5, 15, null, 6, 12, 21, null, null, 11]);
console.log(inorderTraversal(tree4)); // Output: [5, 6, 10, 11, 12, 15, 21]
Exercises
Write a recursive definition for in-order traversal of a binary tree, including the base case and the recursive step.
View Our Solution Work in Code Editor
Base Case
As in the previous problem, the base case occurs when the node is null. In this scenario, we will return from the function to prevent accessing the val property of null, which would raise an error.
Base Case: Return from the function if node is null.
Recursive Definition
Like in the preorder traversal, we must follow a pattern we learned about earlier, but this time the LNR pattern. When we say go left, we mean perform the inorder traversal on the left child. When we say process the node, we mean adding the node's value to the result array. Finally, when we say go right, we mean perform the inorder traversal on the right child.
Recursive Definition: Perform an inorder traversal by first recursively calling the function on the current node's left child, then add the node's value to the result array, and finally recursively call the function on the current node's right child.
Now implement the in-order traversal.
View Our Solution Work in Code Editor
function inorderTraversal(root) {
const result = [];
function traverse(node) {
if (node === null) {
return;
}
traverse(node.left);
result.push(node.val);
traverse(node.right);
}
traverse(root);
return result;
}
Identify the time and space complexity of your in-order traversal.
View Our Solution Work in Code Editor
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.