> For the complete documentation index, see [llms.txt](https://docs-57.gitbook.io/data-structure-and-algorithms/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://docs-57.gitbook.io/data-structure-and-algorithms/problems/tree/binary-tree-inorder-traversal.md).

# Binary Tree Inorder Traversal

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

![image](https://github.com/VikashChauhan51/algorithms/assets/14816038/50e92fd0-02b3-4865-b26f-0693d56214b2)

### Solution

```csharp
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public IList<int> InorderTraversal(TreeNode root) {
        
        List<int> ans=new List<int>();
        if(root == null){
            return ans;
        }
       
        TreeNode curr = root;
        
        while(curr != null){
            
            
            if(curr.left == null){
                ans.Add(curr.val);
                curr = curr.right;
            }
            
            else{
                
                TreeNode prev = curr.left;
                
                while(prev.right!=null && prev.right != curr){
                    prev = prev.right;
                }
                
                if(prev.right == null){
                    prev.right = curr;
                    curr = curr.left;
                    
                }
                
                else{
                    prev.right = null;
                    ans.Add(curr.val);
                    curr = curr.right;
                }
            }            
            
        }
        
        return ans;
        
    }
}
```

* **Time Complexity**: The time complexity of this algorithm is **O(n)**, where n is the number of nodes in the binary tree. This is because the algorithm visits each node twice: once when it first reaches the node and again when it returns to the node after visiting its left subtree.
* **Space Complexity**: The space complexity of this algorithm is **O(1)**, because it doesn't use any additional data structures, such as a stack or a queue, to perform the traversal. The only additional space used by the algorithm is the constant amount of space required for the `curr` and `prev` pointers and the `ans` list to store the result.