Inorder Traversal - Amazon Top Interview Questions

                        Solution in C++ :

vector<int> solve(Tree* root) {  // Morris traversal - Time: O(N), Space: O(1)
    vector<int> inorder;

    while (root) {
        if (root->left) {
            Tree* predecessor = root->left;
            while (predecessor->right && predecessor->right != root)
                predecessor = predecessor->right;

            if (predecessor->right) {
                inorder.push_back(root->val);
                root = root->right;
                predecessor->right = nullptr;
            } else {
                predecessor->right = root;
                root = root->left;
            }
        } else {
            inorder.push_back(root->val);
            root = root->right;
        }
    }

    return inorder;
}
                    

                        Solution in Java :

import java.util.*;

/**
 * public class Tree {
 *   int val;
 *   Tree left;
 *   Tree right;
 * }
 */
class Solution {
    public int[] solve(Tree root) {
        List<Integer> list = new ArrayList<>();
        list = inOrder(root, new ArrayList<>());
        int[] arr = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            arr[i] = list.get(i);
        }
        return arr;
    }
    public List<Integer> inOrder(Tree root, List<Integer> list) {
        if (root == null)
            return list;
        Stack<Tree> st = new Stack<>();
        Tree temp = root;
        while (temp != null || st.size() > 0) {
            while (temp != null) {
                st.push(temp);
                temp = temp.left;
            }

            temp = st.pop();
            list.add(temp.val);
            temp = temp.right;
        }
        return list;
    }
}
                    

                        Solution in Python : 
                            
class Solution:
    def solve(self, root):
        if not root:
            return []
        # iteratively
        stack = [root.right, root.val, root.left]
        traversal = []

        while stack:
            currNode = stack.pop()
            if type(currNode) == int:
                traversal.append(currNode)
            elif currNode is None:
                continue
            else:
                stack.extend([currNode.right, currNode.val, currNode.left])

        return traversal