Given the root of a binary tree, return the inorder traversal of its nodes’ values. In inorder traversal, we visit the left subtree first, then the current node, and finally the right subtree.
Table of Contents
Sample Input:
Tree:
1
\
2
/
3
Expected Output:
[1, 3, 2]
In this example, the inorder traversal of the binary tree will give the sequence of node values [1, 3, 2].
Time and Space Complexity:
The time complexity of the algorithm is O(n), where ‘n’ is the number of nodes in the binary tree. We need to visit each node once to perform the inorder traversal. The space complexity is O(h), where ‘h’ is the height of the binary tree. In the worst case, the recursion stack can grow to the height of the tree.
C++ solution:
#include <iostream>
#include <vector>
// Definition for a binary tree node.
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
void inorderTraversalHelper(TreeNode* root, std::vector<int>& result) {
// Base case: if the root is null, return
if (root == nullptr) {
return;
}
// Recursively perform inorder traversal on the left subtree
inorderTraversalHelper(root->left, result);
// Process the current node (add its value to the result vector)
result.push_back(root->val);
// Recursively perform inorder traversal on the right subtree
inorderTraversalHelper(root->right, result);
}
std::vector<int> inorderTraversal(TreeNode* root) {
std::vector<int> result;
inorderTraversalHelper(root, result);
return result;
}
int main() {
// Construct the binary tree for the sample input
TreeNode* root = new TreeNode(1);
root->right = new TreeNode(2);
root->right->left = new TreeNode(3);
// Perform the inorder traversal of the binary tree
std::vector<int> inorderResult = inorderTraversal(root);
// Print the result
std::cout << "Inorder Traversal: [";
for (int i = 0; i < inorderResult.size(); ++i) {
std::cout << inorderResult[i];
if (i < inorderResult.size() - 1) {
std::cout << ", ";
}
}
std::cout << "]" << std::endl;
// Don't forget to free the allocated memory
// ...
return 0;
}
The inorderTraversal function performs the inorder traversal of the binary tree. It calls the inorderTraversalHelper function, which is a recursive helper function to traverse the tree and collect the node values in the result vector.
In the given example, the function will correctly perform the inorder traversal of the binary tree and the output will be [1, 3, 2].
As mentioned earlier, the time complexity is O(n) as we need to visit each node once, and the space complexity is O(h) due to the recursion stack, where ‘h’ is the height of the binary tree.