Binary Tree Inorder Traversal LeetCode Solution

Problem Statement:

Binary Tree Inorder Traversal LeetCode solution

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:

1. We will do recursion to find the binary tree inorder traversal. of a tree.

2. In order traversal means first to traverse the left subtree, then the root of the tree, at last, the right subtree (left->root->right).

3. The Base condition of our recursion will be when we reach the leaf node i.e. root will be null.

4. Finally, we’ll be left with binary tree inorder traversal.

Code:

Binary Tree Inorder Traversal C++ solution:

class Solution {
public:
    #define ll int
   
    void rec(TreeNode *root,vector<ll>&v)
    {
        if(root==NULL)
            return;
        rec(root->left,v);
        v.push_back(root->val);
        rec(root->right,v);
    }
    vector<int> inorderTraversal(TreeNode* root) {
         vector<ll>v;
        rec(root,v);
        return v;
    }
};

Binary Tree Inorder Traversal Java solution:

class Solution {
    void rec(TreeNode root,List<Integer> ans)
    {
        if(root==null)
            return;
        rec(root.left,ans);
        ans.add(root.val);
        rec(root.right,ans);
    }
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer>ans= new ArrayList<>();
        rec(root,ans);
        return ans;
    }
}

Complexity analysis of Binary Tree Inorder Traversal LeetCode solution:

Time Complexity:

Time complexity will be o(n). We are traveling every node only once.

Space Complexity:

Space complexity will be o(n). We are storing the value of every node for our traversal that’s why we are taking space of o(n).