Leetcode: 94. Binary Tree Inorder Traversal (Brute force)

Binary Tree Inorder Traversal

Given the root of a binary tree, return the inorder traversal of its nodes' values.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector inorderTraversal(TreeNode* root) {
        vector res; 
        helper(root, res);
        return res;
    }
    void helper(TreeNode* root, vector& res)
    {
        if (root != nullptr)
        {
            helper(root->left, res);
            res.push_back(root->val);
            helper(root->right, res);
        }
    }
}

Example

Input:

    1
     \
      2
     /
    3

Output: [1, 3, 2]

Complexity Analysis

The time complexity of the inorderTraversal function is O(n), where n is the number of nodes in the binary tree. This is because we need to visit each node once to perform the inorder traversal.

The space complexity is O(n) as well, as we need to store the values of all the nodes in the output vector. In the worst case, the binary tree can be skewed, leading to a recursion depth of n.