Inorder Tree Traversal without Recursion

Last Updated : 02 Oct, 2023

In this post, we have seen in detail about the Inorder traversal and how it is implemented using recursion.

Here in this post, we will discuss methods to implement inorder traversal without using recursion.

Inorder Traversal using Stack:

As we already know, recursion can also be implemented using stack. Here also we can use a stack to perform inorder traversal of a Binary Tree. Below is the algorithm for traversing a binary tree using stack.

Create an empty stack (say S).
Initialize the current node as root.
Push the current node to S and set current = current->left until current is NULL
If current is NULL and the stack is not empty then:
- Pop the top item from the stack.
- Print the popped item and set current = popped_item->right
- Go to step 3.
If current is NULL and the stack is empty then we are done.

Illustration:

See the below illustration for a better understanding.

Let us consider the below tree for example

1
/ \
2 3
/ \
4 5

Initially Creates an empty stack: S = NULL and set current as address of root: current -> 1

current = 1: Pushes the current node and set current = current->left until current is NULL:

current -> 1, push 1: Stack S -> 1

current -> 2, push 2: Stack S -> 2, 1

current -> 4, push 4: Stack S -> 4, 2, 1

current = NULL

Now Pop from S

Pop 4: Stack S -> 2, 1. Print “4”.

current = NULL /*right of 4 */ and go to step 3. Since current is NULL step 3 doesn’t do anything.

Step 4 is repeated and pop again.

Pop 2: Stack S -> 1. Print “2”.

current -> 5 /*right of 2 */ and go to step 3

current = 5: Push 5 to stack and make current = current->left which is NULL

Stack S -> 5, 1. current = NULL

Now pop from S

Pop 5: Stack S -> 1. Print “5”.

current = NULL /*right of 5 */ and go to step 3. Since current is NULL step 3 doesn’t do anything

Step 4 repeated again:

Pop 1: Stack S -> NULL. Print “1”.

current -> 3 /*right of 1 */

current = 3: Pushes 3 to stack and make current NULL

Stack S -> 3

current = NULL

Step 4 pops from S:

Pop 3: Stack S -> NULL. Print “3”.

current = NULL /*right of 3 */

Now the traversal is complete as the stack has become empty.

Below is the implementation of the above approach.

C++

// C++ program to print inorder traversal
// using stack.
 
#include <bits/stdc++.h>
using namespace std;
 
// A binary tree Node has data, pointer to left child
// and a pointer to right child
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
    Node(int data)
    {
        this->data = data;
        left = right = NULL;
    }
};
 
//Iterative function for inorder tree traversal
void inOrder(struct Node* root)
{
    stack<Node*> s;
    Node* curr = root;
 
    while (curr != NULL || s.empty() == false) {
         
        // Reach the left most Node of the
        // curr Node
        while (curr != NULL) {
             
            // Place pointer to a tree node on
            // the stack before traversing
            // the node's left subtree
            s.push(curr);
            curr = curr->left;
        }
 
        // Current must be NULL at this point
        curr = s.top();
        s.pop();
 
        cout << curr->data << " ";
 
        // we have visited the node and its
        // left subtree.  Now, it's right
        // subtree's turn
        curr = curr->right;
 
    }
}
 
// Driver program to test above functions
int main()
{
    /* Constructed binary tree is
              1
            /   \
          2      3
        /  \
      4     5
    */
    struct Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
 
    inOrder(root);
    return 0;
}

C

#include <stdio.h>
#include <stdlib.h>
#define bool int
 
// A binary tree tNode has data, pointer to left child
// and a pointer to right child
struct tNode {
    int data;
    struct tNode* left;
    struct tNode* right;
};
 
// Structure of a stack node. Linked List implementation is
// used for stack. A stack node contains a pointer to tree
// node and a pointer to next stack node
struct sNode {
    struct tNode* t;
    struct sNode* next;
};
 
// Stack related functions
void push(struct sNode** top_ref, struct tNode* t);
struct tNode* pop(struct sNode** top_ref);
bool isEmpty(struct sNode* top);
 
// Iterative function for inorder tree traversal
void inOrder(struct tNode* root)
{
    // Set current to root of binary tree
    struct tNode* current = root;
   
    // Initialize stack s
    struct sNode* s = NULL;
    bool done = 0;
 
    while (!done) {
         
        // Reach the left most tNode of the current tNode
        if (current != NULL) {
             
            // Place pointer to a tree node on the stack
            // before traversing the node's left subtree
            push(&s, current);
            current = current->left;
        }
 
        // Backtrack from the empty subtree and visit the
        // tNode at the top of the stack; however, if the
        // stack is empty, you are done
        else {
            if (!isEmpty(s)) {
                current = pop(&s);
                printf("%d ", current->data);
 
                // we have visited the node and its left
                // subtree. Now, it's right subtree's turn
                current = current->right;
            }
            else
                done = 1;
        }
    }
}
 
// Function to push an item to sNode
void push(struct sNode** top_ref, struct tNode* t)
{
    // Allocate tNode
    struct sNode* new_tNode
        = (struct sNode*)malloc(sizeof(struct sNode));
 
    if (new_tNode == NULL) {
        printf("Stack Overflow \n");
        getchar();
        exit(0);
    }
 
    // Put in the data
    new_tNode->t = t;
 
    // Link the old list of the new tNode
    new_tNode->next = (*top_ref);
 
    // Move the head to point to the new tNode
    (*top_ref) = new_tNode;
}
 
// The function returns true if stack is empty,
// otherwise false
bool isEmpty(struct sNode* top)
{
    return (top == NULL) ? 1 : 0;
}
 
// Function to pop an item from stack
struct tNode* pop(struct sNode** top_ref)
{
    struct tNode* res;
    struct sNode* top;
 
    // If sNode is empty then error
    if (isEmpty(*top_ref)) {
        printf("Stack Underflow \n");
        getchar();
        exit(0);
    }
    else {
        top = *top_ref;
        res = top->t;
        *top_ref = top->next;
        free(top);
        return res;
    }
}
 
// Helper function that allocates a new tNode with the
// given data and NULL left and right pointers.
struct tNode* newtNode(int data)
{
    struct tNode* tNode
        = (struct tNode*)malloc(sizeof(struct tNode));
    tNode->data = data;
    tNode->left = NULL;
    tNode->right = NULL;
 
    return (tNode);
}
 
// Driver program to test above functions
int main()
{
    /* Constructed binary tree is
              1
            /   \
          2      3
        /  \
      4     5
    */
    struct tNode* root = newtNode(1);
    root->left = newtNode(2);
    root->right = newtNode(3);
    root->left->left = newtNode(4);
    root->left->right = newtNode(5);
 
    inOrder(root);
 
    getchar();
    return 0;
}

Java

// Non-recursive java program for inorder traversal
 
import java.util.Stack;
 
// Class containing left and right child of
// current node and key value
class Node
{
    int data;
    Node left, right;
 
    public Node(int item)
    {
        data = item;
        left = right = null;
    }
}
 
// Class to print the inorder traversal
class BinaryTree
{
    Node root;
    void inorder()
    {
        if (root == null)
            return;
 
 
        Stack<Node> s = new Stack<Node>();
        Node curr = root;
 
        // Traverse the tree
        while (curr != null || s.size() > 0)
        {
 
            // Reach the left most Node of the
            // curr Node
            while (curr !=  null)
            {
                // Place pointer to a tree node on
                // the stack before traversing
                // the node's left subtree
                s.push(curr);
                curr = curr.left;
            }
 
            // Current must be NULL at this point
            curr = s.pop();
 
            System.out.print(curr.data + " ");
 
            // we have visited the node and its
            // left subtree. Now, it's right
            // subtree's turn
            curr = curr.right;
        }
    }
 
    public static void main(String args[])
    {
        // Creating a binary tree and entering
        // the nodes
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(5);
        tree.inorder();
    }
}

Python3

# Python program to do inorder traversal without recursion
 
 
# A binary tree node
class Node:
     
    # Constructor to create a new node
    def __init__(self, data):
        self.data = data 
        self.left = None
        self.right = None
 
 
# Iterative function for inorder tree traversal
def inOrder(root):
     
    # Set current to root of binary tree
    current = root
     
    # Initialize stack
    stack = []
     
    while True:
         
        # Reach the left most Node of the current Node
        if current is not None:
             
            # Place pointer to a tree node on the stack 
            # before traversing the node's left subtree
            stack.append(current)
         
            current = current.left
         
        # BackTrack from the empty subtree and visit the Node
        # at the top of the stack; however, if the stack is 
        # empty you are done
        elif(stack):
            current = stack.pop()
            print(current.data, end=" ")
         
            # We have visited the node and its left 
            # subtree. Now, it's right subtree's turn
            current = current.right 
 
        else:
            break
     
    print()
 
 
# Driver program to test above function
if __name__ == '__main__':
     
    """ Constructed binary tree is
            1
          /   \
         2     3
       /  \
      4    5   """
     
    root = Node(1)
    root.left = Node(2)
    root.right = Node(3)
    root.left.left = Node(4)
    root.left.right = Node(5)
     
    inOrder(root)
 
# This code is contributed by Nikhil Kumar Singh(nickzuck_007)

C#

// Non-recursive C# program for inorder traversal
using System;
using System.Collections.Generic;
 
// Class containing left and right child of
// current node and key value
public class Node {
    public int data;
    public Node left, right;
 
    public Node(int item)
    {
        data = item;
        left = right = null;
    }
}
 
// Class to print the inorder traversal
public class BinaryTree {
    public Node root;
    public virtual void inorder()
    {
        if (root == null) {
            return;
        }
 
        Stack<Node> s = new Stack<Node>();
        Node curr = root;
 
        // Traverse the tree
        while (curr != null || s.Count > 0) {
 
            // Reach the left most Node of the
            // curr Node
            while (curr != null) {
                 
                // Place pointer to a tree node on
                // the stack before traversing
                // the node's left subtree
                s.Push(curr);
                curr = curr.left;
            }
 
            // Current must be NULL at this point
            curr = s.Pop();
 
            Console.Write(curr.data + " ");
 
            // we have visited the node and its
            // left subtree. Now, it's right
            // subtree's turn
            curr = curr.right;
        }
    }
 
    public static void Main(string[] args)
    {
        // Creating a binary tree and entering
        // the nodes
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(5);
        tree.inorder();
    }
}
 
// This code is contributed by Shrikant13

Javascript

// Non-recursive javascript program for inorder traversal
 
// Class containing left and right child of
// current node and key value
class Node {
 
     constructor(item) {
        this.data = item;
        this.left = this.right = null;
    }
}
 
// Class to print the inorder traversal
 
    var root;
 
    function inorder()
    {
        if (root == null)
            return;
 
        var s = [];
        var curr = root;
 
        // traverse the tree
        while (curr != null || s.length > 0)
        {
 
            // Reach the left most Node of the curr Node
            while (curr != null)
            {
                // Place pointer to a tree node on the stack 
                // before traversing the node's left subtree
                s.push(curr);
                curr = curr.left;
            }
 
            // Current must be NULL at this point
            curr = s.pop();
 
            console.log(curr.data + " ");
 
            // We have visited the node and its left subtree. 
            // Now, it's right subtree's turn
            curr = curr.right;
        }
    }
     
        // Creating a binary tree and entering the nodes
        root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        inorder();
 
// This code is contributed by umadevi9616

Output

4 2 5 1 3

Time Complexity: O(N) where N is the number of nodes in the tree
Auxiliary Space: O(N)

Inorder traversal using Morris Traversal:

Following is the algorithm to implement inorder traversal using Morris traversal:

Initialize the current node as root.
While current is not null, check if it has a left child.
- If there is no left child, print the current node and move to the right child of the current node.
- Otherwise, find the rightmost node of the left subtree or the node whose right child is the current node:
  - If the right child is NULL, make current as the right child and move to the left child of current.
  - If the right child is the current node itself, print current node, make the right child NULL and move to the right child of the current node.

Below is the implementation of the above approach

C++

// C++ program for Inorder Morris Traversal
#include <bits/stdc++.h>
using namespace std;
 
// A binary tree tNode has data, a pointer to left child
// and a pointer to right child
struct tNode {
    int data;
    struct tNode* left;
    struct tNode* right;
};
 
// Function to traverse the binary tree 
// without recursion and without stack
void inOrder(struct tNode* root)
{
    struct tNode *current, *pre;
 
    if (root == NULL)
        return;
 
    current = root;
    while (current != NULL) {
 
        if (current->left == NULL) {
            cout << current->data << " ";
            current = current->right;
        }
        else {
 
            // Find the inorder predecessor of current
            pre = current->left;
            while (pre->right != NULL
                   && pre->right != current)
                pre = pre->right;
 
            // Make current as the right child of its
            // inorder predecessor 
            if (pre->right == NULL) {
                pre->right = current;
                current = current->left;
            }
 
            // Revert the changes made in the 'if' part to
            // restore the original tree i.e., fix the right
            // child of predecessor
            else {
                pre->right = NULL;
                cout << current->data << " ";
                current = current->right;
            }
        }
    }
}
 
struct tNode* newtNode(int data)
{
    struct tNode* node = new tNode;
    node->data = data;
    node->left = NULL;
    node->right = NULL;
 
    return (node);
}
 
// Driver code
int main()
{
    struct tNode* root = newtNode(1);
    root->left = newtNode(2);
    root->right = newtNode(3);
    root->left->left = newtNode(4);
    root->left->right = newtNode(5);
 
    inOrder(root);
 
    return 0;
}
// This code is contributed by Raunak Singh

Java

// Java program for Inorder Morris Traversal
 
import java.io.*;
import java.util.*;
 
class Node {
    int data;
    Node left, right;
 
    public Node(int item)
    {
        data = item;
        left = right = null;
    }
}
 
public class GFG {
    Node root;
    void inOrder()
    {
        Node cur = root;
 
        while (cur != null) {
            if (cur.left == null) {
                System.out.print(cur.data + " ");
                cur = cur.right;
            }
            else {
                Node temp = cur.left;
                while (temp.right != null
                       && temp.right != cur)
                    temp = temp.right;
 
                if (temp.right == null) {
                    temp.right = cur;
                    cur = cur.left;
                }
                else {
                    temp.right = null;
                    System.out.print(cur.data + " ");
                    cur = cur.right;
                }
            }
        }
    }
   
    // Driver code
    public static void main(String args[])
    {
        GFG tree = new GFG();
        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(5);
        tree.inOrder();
    }
}
// This code is contributed by Raunak Singh

Python3

class TreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
 
 
def morris_traversal(root):
    current = root
 
    while current:
        if current.left is None:
            print(current.data, end=" ")
            current = current.right
        else:
            # Find the inorder predecessor of current
            pre = current.left
            while pre.right and pre.right != current:
                pre = pre.right
 
            # Make current as the right child of its inorder predecessor
            if pre.right is None:
                pre.right = current
                current = current.left
            # Revert the changes made to restore the original tree and print current node
            else:
                pre.right = None
                print(current.data, end=" ")
                current = current.right
 
 
# Driver program to test above functions
if __name__ == '__main__':
    """
    Constructed binary tree is
            1
          /   \
         2     3
       /   \
      4     5
    """
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.left.left = TreeNode(4)
    root.left.right = TreeNode(5)
 
    morris_traversal(root)

C#

// C# program for Inorder Morris Traversal
 
using System;
 
// A binary tree tNode has data, a pointer to left child
// and a pointer to right child
class Node {
    public int data;
    public Node left, right;
 
    public Node(int item)
    {
        data = item;
        left = right = null;
    }
}
 
class GFG {
    public Node root;
 
    // Function to traverse the binary tree without
    // recursion and without stack
    public void inOrder()
    {
        Node cur = root;
 
        while (cur != null) {
 
            if (cur.left == null) {
                Console.Write(cur.data + " ");
                cur = cur.right;
            }
            else {
                // Find the inorder predecessor of current
                Node temp = cur.left;
                while (temp.right != null
                       && temp.right != cur)
                    temp = temp.right;
 
                // Make current as the right child of its
                // inorder predecessor
                if (temp.right == null) {
                    temp.right = cur;
                    cur = cur.left;
                }
 
                // Revert the changes made in the 'if' part
                // to restore the original tree i.e., fix
                // the right child of predecessor
                else {
                    temp.right = null;
                    Console.Write(cur.data + " ");
                    cur = cur.right;
                }
            }
        }
    }
 
    // Driver code
    static void Main(string[] args)
    {
        GFG tree = new GFG();
        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(5);
        tree.inOrder();
    }
}

Javascript

class TreeNode {
  constructor(data) {
    this.data = data;
    this.left = null;
    this.right = null;
  }
}
 
function morrisTraversal(root) {
  let current = root;
 
  while (current) {
    if (current.left === null) {
      console.log(current.data + " ");
      current = current.right;
    } else {
      // Find the inorder predecessor of current
      let pre = current.left;
      while (pre.right && pre.right !== current) {
        pre = pre.right;
      }
 
      // Make current as the right child of its inorder predecessor
      if (pre.right === null) {
        pre.right = current;
        current = current.left;
      } else {
        pre.right = null;
        console.log(current.data + " ");
        current = current.right;
      }
    }
  }
}
 
// Driver program to test above functions
 
// Constructed binary tree
/*
    1
  /   \
 2     3
/   \
4     5
*/
const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
 
morrisTraversal(root);
 
// This code is contributed by Dwaipayan Bandyopadhyay

Output

4 2 5 1 3

Time Complexity: O(N), where N is the number of nodes in a tree.
Auxiliary Space: O(1)

Inorder Traversal using Iterative way

Below is the Implementation of the above approach:

C++

#include <bits/stdc++.h>
 
using namespace std;
 
struct node {
  int data;
  struct node * left, * right;
};
 
vector < int > inOrderTrav(node * curr) {
  vector < int > inOrder;
  stack < node * > s;
  while (true) {
    if (curr != NULL) {
      s.push(curr);
      curr = curr -> left;
    } else {
      if (s.empty()) break;
      curr = s.top();
      inOrder.push_back(curr -> data);
      s.pop();
      curr = curr -> right;
    }
  }
  return inOrder;
}
 
struct node * newNode(int data) {
  struct node * node = (struct node * ) malloc(sizeof(struct node));
  node -> data = data;
  node -> left = NULL;
  node -> right = NULL;
 
  return (node);
}
 
int main() {
 
  struct node * root = newNode(1);
  root -> left = newNode(2);
  root -> right = newNode(3);
  root -> left -> left = newNode(4);
  root -> left -> right = newNode(5);
  root -> left -> right -> left = newNode(8);
  root -> right -> left = newNode(6);
  root -> right -> right = newNode(7);
  root -> right -> right -> left = newNode(9);
  root -> right -> right -> right = newNode(10);
 
  vector < int > inOrder;
  inOrder = inOrderTrav(root);
 
  cout << "The inOrder Traversal is : ";
  for (int i = 0; i < inOrder.size(); i++) {
    cout << inOrder[i] << " ";
  }
  return 0;
}

Java

/*package whatever //do not write package name here */
 
import java.util.*;
 
class Node {
    int data;
    Node left, right;
    Node(int data) {
        this.data = data;
        left = null;
        right = null;
    }
}
class gfg {
    static ArrayList < Integer > inOrderTrav(Node curr) {
        ArrayList < Integer > inOrder = new ArrayList < > ();
        Stack < Node > s = new Stack < > ();
        while (true) {
            if (curr != null) {
                s.push(curr);
                curr = curr.left;
            } else {
                if (s.isEmpty()) break;
                curr = s.peek();
                inOrder.add(curr.data);
                s.pop();
                curr = curr.right;
            }
        }
        return inOrder;
    }
 
    public static void main(String args[]) {
 
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.left.right.left = new Node(8);
        root.right.left = new Node(6);
        root.right.right = new Node(7);
        root.right.right.left = new Node(9);
        root.right.right.right = new Node(10);
 
        ArrayList < Integer > inOrder;
        inOrder = inOrderTrav(root);
 
        System.out.println("The inOrder Traversal is : ");
        for (int i = 0; i < inOrder.size(); i++) {
            System.out.print(inOrder.get(i) + " ");
        }
    }
}

Python3

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
 
def inOrderTrav(curr):
    inOrder = []
    s = []
    while True:
        if curr:
            s.append(curr)
            curr = curr.left
        else:
            if not s:
                break
            curr = s[-1]
            inOrder.append(curr.data)
            s.pop()
            curr = curr.right
    return inOrder
 
if __name__ == "__main__":
    root = Node(1)
    root.left = Node(2)
    root.right = Node(3)
    root.left.left = Node(4)
    root.left.right = Node(5)
    root.left.right.left = Node(8)
    root.right.left = Node(6)
    root.right.right = Node(7)
    root.right.right.left = Node(9)
    root.right.right.right = Node(10)
 
    inOrder = inOrderTrav(root)
 
    print("The inOrder Traversal is : ")
    for data in inOrder:
        print(data, end=" ")

C#

using System;
using System.Collections.Generic;
 
public class Node
{
    public int data;
    public Node left;
    public Node right;
}
 
public class InOrderTraversal
{
    // Function to perform iterative in-order traversal
    public static List<int> InOrderTrav(Node curr)
    {
        List<int> inOrder = new List<int>();
        Stack<Node> stack = new Stack<Node>();
         
        while (true)
        {
            // Traverse left subtree until current node is null
            if (curr != null)
            {
                stack.Push(curr);
                curr = curr.left;
            }
            else
            {
                // If current node is null, pop a node from the stack,
                // add its data to the in-order list, and traverse its right subtree
                if (stack.Count == 0)
                    break;
                 
                curr = stack.Pop();
                inOrder.Add(curr.data);
                curr = curr.right;
            }
        }
         
        return inOrder;
    }
 
    // Function to create a new binary tree node
    public static Node NewNode(int data)
    {
        Node node = new Node();
        node.data = data;
        node.left = null;
        node.right = null;
 
        return node;
    }
 
    public static void Main()
    {
        // Create the binary tree
        Node root = NewNode(1);
        root.left = NewNode(2);
        root.right = NewNode(3);
        root.left.left = NewNode(4);
        root.left.right = NewNode(5);
        root.left.right.left = NewNode(8);
        root.right.left = NewNode(6);
        root.right.right = NewNode(7);
        root.right.right.left = NewNode(9);
        root.right.right.right = NewNode(10);
 
        // Perform in-order traversal
        List<int> inOrder = new List<int>();
        inOrder = InOrderTrav(root);
 
        // Print the in-order traversal result
        Console.Write("The inOrder Traversal is : ");
        foreach (int val in inOrder)
        {
            Console.Write(val + " ");
        }
    }
}
 
// This code is contributed by shivamgupta310570

Javascript

class Node {
    constructor(data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}
 
function inOrderTrav(curr) {
    const inOrder = [];
    const stack = [];
 
    while (true) {
        // Traverse left subtree until current node is null
        if (curr !== null) {
            stack.push(curr);
            curr = curr.left;
        } else {
            // If current node is null, pop a node from the stack,
            // add its data to the in-order list, and traverse its right subtree
            if (stack.length === 0)
                break;
 
            curr = stack.pop();
            inOrder.push(curr.data);
            curr = curr.right;
        }
    }
 
    return inOrder;
}
 
function newNode(data) {
    const node = new Node(data);
    return node;
}
 
// Create the binary tree
const root = newNode(1);
root.left = newNode(2);
root.right = newNode(3);
root.left.left = newNode(4);
root.left.right = newNode(5);
root.left.right.left = newNode(8);
root.right.left = newNode(6);
root.right.right = newNode(7);
root.right.right.left = newNode(9);
root.right.right.right = newNode(10);
 
// Perform in-order traversal
const inOrder = inOrderTrav(root);
 
// Print the in-order traversal result
console.log("The inOrder Traversal is: " + inOrder.join(" "));
 
// This code is contributed by rambabuguphka

Output

The inOrder Traversal is : 4 2 8 5 1 6 3 9 7 10

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

See this post for another approach of Inorder Tree Traversal without recursion and without stack!

Please write comments if you find any bug in above code/algorithm, or want to share more information about stack based Inorder Tree Traversal.

GeeksforGeeks

Improve

Previous Article

Difference between an array and a tree

Types of Trees in Data Structures

Similar Reads

Inorder Tree Traversal without recursion and without stack!

Using Morris Traversal, we can traverse the tree without using stack and recursion. The idea of Morris Traversal is based on Threaded Binary Tree. In this traversal, we first create links to Inorder successor and print the data using these links, and finally revert the changes to restore original tree. 1. Initialize current as root 2. While current

Inorder Non-threaded Binary Tree Traversal without Recursion or Stack

We have discussed Thread based Morris Traversal. Can we do inorder traversal without threads if we have parent pointers available to us? Input: Root of Below Tree [Every node of tree has parent pointer also] 10 / \ 5 100 / \ 80 120 Output: 5 10 80 100 120 The code should not extra space (No Recursion and stack) In inorder traversal, we follow "left

Postorder traversal of Binary Tree without recursion and without stack

Given a binary tree, perform postorder traversal. Prerequisite - Inorder/preorder/postorder traversal of tree We have discussed the below methods for postorder traversal. 1) Recursive Postorder Traversal. 2) Postorder traversal using Stack. 2) Postorder traversal using two Stacks. Approach 1 The approach used is based on using an unordered set to k

Pre Order, Post Order and In Order traversal of a Binary Tree in one traversal | (Using recursion)

Given a binary tree, the task is to print all the nodes of the binary tree in Pre-order, Post-order, and In-order in one iteration. Examples: Input: Output: Pre Order: 1 2 4 5 3 6 7 Post Order: 4 5 2 6 7 3 1 In Order: 4 2 5 1 6 3 7 Input: Output: Pre Order: 1 2 4 8 12 5 9 3 6 7 10 11 Post Order: 12 8 4 9 5 2 6 10 11 7 3 1 In Order: 8 12 4 2 9 5 1 6

Cartesian tree from inorder traversal | Segment Tree

Given an in-order traversal of a cartesian tree, the task is to build the entire tree from it. Examples: Input: arr[] = {1, 5, 3} Output: 1 5 3 5 / \ 1 3 Input: arr[] = {3, 7, 4, 8} Output: 3 7 4 8 8 / 7 / \ 3 4 Approach: We have already seen an algorithm here that takes O(NlogN) time on an average but can get to O(N2) in the worst case.In this art

Preorder Traversal of N-ary Tree Without Recursion

Given an n-ary tree, print preorder traversal of it. Example : Preorder traversal of below tree is A B K N M J F D G E C H I L The idea is to use stack like iterative preorder traversal of binary tree. Create an empty stack to store nodes. Push the root node to the stack. Run a loop while the stack is not empty Pop the top node from stack. Print th

Check if given inorder and preorder traversals are valid for any Binary Tree without building the tree

cGiven two arrays pre[] and in[] representing the preorder and inorder traversal of the binary tree, the task is to check if the given traversals are valid for any binary tree or not without building the tree. If it is possible, then print Yes. Otherwise, print No. Examples: Input: pre[] = {1, 2, 4, 5, 7, 3, 6, 8}, in[] = {4, 2, 5, 7, 1, 6, 8, 3}Ou

Construct Special Binary Tree from given Inorder traversal

Given Inorder Traversal of a Special Binary Tree in which the key of every node is greater than keys in left and right children, construct the Binary Tree and return root. Examples: Input: inorder[] = {5, 10, 40, 30, 28} Output: root of following tree 40 / \ 10 30 / \ 5 28 Input: inorder[] = {1, 5, 10, 40, 30, 15, 28, 20} Output: root of following

Calculate height of Binary Tree using Inorder and Level Order Traversal

Given inorder traversal and Level Order traversal of a Binary Tree. The task is to calculate the height of the tree without constructing it. Example: Input : Input: Two arrays that represent Inorder and level order traversals of a Binary Tree in[] = {4, 8, 10, 12, 14, 20, 22}; level[] = {20, 8, 22, 4, 12, 10, 14}; Output : 4 The binary tree that ca

Check if Inorder traversal of a Binary Tree is palindrome or not

Given a binary tree and the task if to check if its Inorder Sequence is a palindrome or not. Examples: Input: Output: True Explanation: The Inorder sequence of the tree is "bbaaabb" which is a palindromic string.Input: Output: False Explanation: The Inorder sequence of the tree is "bbdaabb" which is not a palindromic string. Approach: To solve the

Article Tags :

Practice Tags :