Binary Tree Inorder Traversal LeetCode Solution

Difficulty Level Easy
Frequently asked in Adobe Amazon Apple Bloomberg Facebook Goldman Sachs Google Microsoft Oracle Yahoo
Binary Tree Depth First Search Stack TreeViews 141

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:

Binary Tree Inorder Traversal LeetCode Solution

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).

 

Translate »