Sponsored
Sponsored
This approach uses recursion to traverse the binary tree. Inorder traversal involves visiting the left subtree, the root node, and then the right subtree. The base case for the recursion is to return if the current node is null.
Time Complexity: O(n), where n is the number of nodes in the binary tree.
Space Complexity: O(n) due to the recursion stack.
1#include <stdio.h>
2#include <stdlib.h>
3
4struct TreeNode {
5 int val;
6 struct TreeNode *left;
7 struct TreeNode *right;
8};
9
10void inorderTraversalHelper(struct TreeNode* root, int* returnSize, int* result) {
11 if (!root) return;
12 inorderTraversalHelper(root->left, returnSize, result);
13 result[(*returnSize)++] = root->val;
14 inorderTraversalHelper(root->right, returnSize, result);
15}
16
17int* inorderTraversal(struct TreeNode* root, int* returnSize) {
18 *returnSize = 0;
19 int* result = (int*)malloc(100 * sizeof(int));
20 inorderTraversalHelper(root, returnSize, result);
21 return result;
22}The C solution defines a helper function inorderTraversalHelper to perform the recursion. The function is called with the current node and a result array to store the values. This implementation assumes a maximum of 100 nodes and allocates space accordingly, which is suitable for the problem constraints but would require dynamic reallocation in a more general scenario.
In this approach, we use a stack to perform an iterative inorder traversal. The stack is utilized to track the nodes to be visited. This method mimics the recursive behavior by explicitly using a stack to push left children until reaching a null entry, then processes the nodes and explores the right subtrees.
Time Complexity: O(n)
Space Complexity: O(n)
1import
In Java, the Stack class is used to simulate the recursive stack behavior needed for inorder traversal. Nodes on the left are pushed, backtracked, and processed as defined by the inorder traversal rules.