Binary Tree Inorder Traversal

Write a program to find the Binary Tree Inorder Traversal.

Example 1:

Input: root = [1,2]
Output: [2,1]

Example 2:

Input: root = [1,null,2,3]
Output: [1,3,2]

Approach 1: Recursion

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class BinaryTreeInorderTraversalRecursion {
    public static void main(String[] args) {
        TreeNode tree = new TreeNode(1);
        tree.right = new TreeNode(2);
        tree.right.left = new TreeNode(3);
        inorder(tree);
        System.out.println("Tree Inorder is " + Arrays.asList(result));
    }

    static List<Integer> result = new ArrayList<>();

    public static void inorder(TreeNode root) {
        if (root == null)
            return;

        // visit left node
        inorder(root.left);
        // Add root value
        result.add(root.val);
        // visit right node
        inorder(root.right);

    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

// Time Complexity: O(n)

C++

#include <bits/stdc++.h>
using namespace std;
//struct for treenode
struct TreeNode{
    int data;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int data)
    {
        this->data=data;
        this->left=NULL;
        this->right=NULL;
    }
};
//Function to find inorder Traversal
//of tree
void inorderTraversal(TreeNode *root)
{
    //Base Case
    if(root==NULL)
       return;
    //visit left subtree
    inorderTraversal(root->left);
    // visit root
    cout<<root->data<<" ";
    //visit right subtree
    inorderTraversal(root->right);
}
int main()
{
    TreeNode *tree=new TreeNode(1);
    tree->right=new TreeNode(2);
    tree->right->left=new TreeNode(3);
    cout<<"Inorder Traversal\n";
    inorderTraversal(tree);
    return 0;
}
//Time Complexity: O(n)

Approach 2: Iterative

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

public class BinaryTreeInorderTraversalIteration {
    public static void main(String[] args) {
        TreeNode tree = new TreeNode(1);
        tree.right = new TreeNode(2);
        tree.right.left = new TreeNode(3);
        inorder(tree);
        System.out.println("Tree Inorder is " + Arrays.asList(result));
    }

    static List<Integer> result = new ArrayList<>();

    static Stack<TreeNode> stack = new Stack<>();

    public static List<Integer> inorder(TreeNode root) {

        if (root == null)
            return result;

        TreeNode c = root;

        while (c != null || !stack.isEmpty()) {
            if (c != null) {
                stack.push(c);
                c = c.left;
            } else {
                c = stack.pop();
                result.add(c.val);
                c = c.right;
            }
        }
        return result;
    }

}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

// Time Complexity: O(n)

C++

#include <bits/stdc++.h>
using namespace std;
//struct for treenode
struct TreeNode{
    int data;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int data)
    {
        this->data=data;
        this->left=NULL;
        this->right=NULL;
    }
};
//Function to find inorder Traversal
//of tree
vector<int> inorderTraversal(TreeNode *root)
{
    vector<int> res;
    stack<TreeNode*> st;
    TreeNode *temp=root;
    while(temp!=NULL||!st.empty())
      {
          if(temp!=NULL)
            {
                st.push(temp);
                temp=temp->left;
            }
          else
          {
              temp=st.top();
              st.pop();
              res.push_back(temp->data);
              temp=temp->right;
          }
          
      }
      return res;
}
int main()
{
    TreeNode *tree=new TreeNode(1);
    tree->right=new TreeNode(2);
    tree->right->left=new TreeNode(3);
    cout<<"Inorder Traversal\n";
    vector<int> res=inorderTraversal(tree);
    int n=res.size();
    for(int i=0;i<n;i++)
       cout<<res[i]<<" ";
    
    return 0;
}
//Time Complexity: O(n)