94. Binary Tree Inorder Traversal

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

Example 1:

Input: root = [1,null,2,3]
Output: [1,3,2]

Example 2:

Input: root = []
Output: []

Example 3:

Input: root = [1]
Output: [1]

Constraints:

• The number of nodes in the tree is in the range [0, 100].
• -100 <= Node.val <= 100

Approach 01:

#include <iostream>
#include <vector>

using namespace std;


//  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<int> inorderTraversal(TreeNode* root) {
        if (root == NULL) return {};

        vector<int> result;

        vector<int> leftResult = inorderTraversal(root->left);
        result.insert(result.end(), leftResult.begin(), leftResult.end());
        result.push_back(root->val);
        vector<int> rightResult = inorderTraversal(root->right);

        result.insert(result.end(), rightResult.begin(), rightResult.end());

        return result;
    }
};

from typing import *

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if root is None:
            return []

        result = []

        result.extend(self.inorderTraversal(root.left))
        result.append(root.val)
        result.extend(self.inorderTraversal(root.right))

        return result

Time Complexity

• Recursive Calls:

  Each node in the binary tree is visited exactly once during the inorder traversal, resulting in \( O(n) \) recursive calls, where \( n \) is the number of nodes in the tree.

• Vector Operations:

  Inserting elements from the left and right subtree traversals and appending the root value take \( O(n) \) time in total as each node’s value is added to the result vector once.

• Overall Time Complexity:

  The overall time complexity of the algorithm is \( O(n) \).

Space Complexity

• Recursive Call Stack:

  The maximum depth of the recursion stack is equal to the height of the tree. In the worst case, the height of the tree can be \( n \) (for a skewed tree), resulting in \( O(n) \) space usage for the call stack.

• Result Vector:

  The result vector stores the values of all \( n \) nodes, resulting in \( O(n) \) space usage.

• Overall Space Complexity:

  The overall space complexity of the algorithm is \( O(n) \).