Inorder Traversal

Problem

Given a Binary Tree, find the In-Order Traversal of it.

Examples:

Example 1:

Input:
       1
     /  \
    3    2
Output: 3 1 2

Example 2:

Input:
        10
     /      \ 
    20       30 
  /    \    /
 40    60  50
Output: 40 20 60 10 50 30

Your task:

You don't need to read input or print anything. Your task is to complete the function inOrder() that takes root node of the tree as input and returns a list containing the In-Order Traversal of the given Binary Tree.

• Expected Time Complexity: $O(N)$
• Expected Auxiliary Space: $O(N)$

Constraints:

• $1 <=$Number of nodes $<= 10^5$
• $0 <=$Data of a node $<= 10^5$

Solution

Python

def InOrder(self,root):
    arr = []
    def traverse(node):
        if node is None:
            return
        traverse(node.left)
        arr.append(node.data)
        traverse(node.right)
    traverse(root)
    return arr

Java

ArrayList<Integer> inOrder(Node root) {
    ArrayList<Integer> arr = new ArrayList<>();
    traverse(root, arr);
    return arr;
}

void traverse(Node node, ArrayList<Integer> arr) {
    if (node == null)
        return;
    traverse(node.left, arr);
    arr.add(node.data);
    traverse(node.right, arr);
}

C++

vector<int> inOrder(Node* root) {
    vector<int> result;
    traverse(root, result);
    return result;
}

void traverse(Node* node, vector<int>& result) {
    if (node == nullptr)
        return;
    traverse(node->left, result);
    result.push_back(node->data);
    traverse(node->right, result);
}

• Time Complexity: $O(N)$
• Auxiliary Space: $O(N)$