Binary Tree Inorder Traversal

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

image

Solution

/**
 * 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.