Open In App

Iterative Preorder Traversal

Last Updated : 22 May, 2024
Summarize
Comments
Improve
Suggest changes
Like Article
Like
Save
Share
Report
News Follow

Given a Binary Tree, write an iterative function to print the Preorder traversal of the given binary tree.
Refer to this for recursive preorder traversal of Binary Tree. To convert an inherently recursive procedure to iterative, we need an explicit stack. 

Following is a simple stack based iterative process to print Preorder traversal. 

  1. Create an empty stack nodeStack and push root node to stack. 
  2. Do the following while nodeStack is not empty. 
    1. Pop an item from the stack and print it. 
    2. Push right child of a popped item to stack 
    3. Push left child of a popped item to stack

The right child is pushed before the left child to make sure that the left subtree is processed first.

C++ 
// C++ program to implement iterative preorder traversal
#include <bits/stdc++.h>

using namespace std;

/* A binary tree node has data, left child and right child */
struct node {
    int data;
    struct node* left;
    struct node* right;
};

/* Helper function that allocates a new node with the given data and
   NULL left and right  pointers.*/
struct node* newNode(int data)
{
    struct node* node = new struct node;
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return (node);
}

// An iterative process to print preorder traversal of Binary tree
void iterativePreorder(node* root)
{
    // Base Case
    if (root == NULL)
        return;

    // Create an empty stack and push root to it
    stack<node*> nodeStack;
    nodeStack.push(root);

    /* Pop all items one by one. Do following for every popped item
       a) print it
       b) push its right child
       c) push its left child
    Note that right child is pushed first so that left is processed first */
    while (nodeStack.empty() == false) {
        // Pop the top item from stack and print it
        struct node* node = nodeStack.top();
        printf("%d ", node->data);
        nodeStack.pop();

        // Push right and left children of the popped node to stack
        if (node->right)
            nodeStack.push(node->right);
        if (node->left)
            nodeStack.push(node->left);
    }
}

// Driver program to test above functions
int main()
{
    /* Constructed binary tree is
            10
          /   \
        8      2
      /  \    /
    3     5  2
  */
    struct node* root = newNode(10);
    root->left = newNode(8);
    root->right = newNode(2);
    root->left->left = newNode(3);
    root->left->right = newNode(5);
    root->right->left = newNode(2);
    iterativePreorder(root);
    return 0;
}
Java 
// Java program to implement iterative preorder traversal
import java.util.Stack;

// A binary tree node
class Node {

    int data;
    Node left, right;

    Node(int item)
    {
        data = item;
        left = right = null;
    }
}

class BinaryTree {

    Node root;

    void iterativePreorder()
    {
        iterativePreorder(root);
    }

    // An iterative process to print preorder traversal of Binary tree
    void iterativePreorder(Node node)
    {

        // Base Case
        if (node == null) {
            return;
        }

        // Create an empty stack and push root to it
        Stack<Node> nodeStack = new Stack<Node>();
        nodeStack.push(root);

        /* Pop all items one by one. Do following for every popped item
         a) print it
         b) push its right child
         c) push its left child
         Note that right child is pushed first so that left is processed first */
        while (nodeStack.empty() == false) {

            // Pop the top item from stack and print it
            Node mynode = nodeStack.peek();
            System.out.print(mynode.data + " ");
            nodeStack.pop();

            // Push right and left children of the popped node to stack
            if (mynode.right != null) {
                nodeStack.push(mynode.right);
            }
            if (mynode.left != null) {
                nodeStack.push(mynode.left);
            }
        }
    }

    // driver program to test above functions
    public static void main(String args[])
    {
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(10);
        tree.root.left = new Node(8);
        tree.root.right = new Node(2);
        tree.root.left.left = new Node(3);
        tree.root.left.right = new Node(5);
        tree.root.right.left = new Node(2);
        tree.iterativePreorder();
    }
}

// This code has been contributed by Mayank Jaiswal
Python 
# Python program to perform iterative preorder traversal

# 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

# An iterative process to print preorder traversal of BT
def iterativePreorder(root):
    
    # Base CAse 
    if root is None:
        return 

    # create an empty stack and push root to it
    nodeStack = []
    nodeStack.append(root)

    # Pop all items one by one. Do following for every popped item
    # a) print it
    # b) push its right child
    # c) push its left child
    # Note that right child is pushed first so that left
    # is processed first */
    while(len(nodeStack) > 0):
        
        # Pop the top item from stack and print it
        node = nodeStack.pop()
        print (node.data, end=" ")
        
        # Push right and left children of the popped node
        # to stack
        if node.right is not None:
            nodeStack.append(node.right)
        if node.left is not None:
            nodeStack.append(node.left)
    
# Driver program to test above function
root = Node(10)
root.left = Node(8)
root.right = Node(2)
root.left.left = Node(3)
root.left.right = Node(5)
root.right.left = Node(2)
iterativePreorder(root)

# This code is contributed by Nikhil Kumar Singh(nickzuck_007)
C# 
// C# program to implement iterative
// preorder traversal
using System;
using System.Collections.Generic;

// A binary tree node
public class Node {
    public int data;
    public Node left, right;

    public Node(int item)
    {
        data = item;
        left = right = null;
    }
}

class GFG {
    public Node root;

    public virtual void iterativePreorder()
    {
        iterativePreorder(root);
    }

    // An iterative process to print preorder
    // traversal of Binary tree
    public virtual void iterativePreorder(Node node)
    {

        // Base Case
        if (node == null) {
            return;
        }

        // Create an empty stack and push root to it
        Stack<Node> nodeStack = new Stack<Node>();
        nodeStack.Push(root);

        /* Pop all items one by one. Do following
       for every popped item 
    a) print it 
    b) push its right child 
    c) push its left child 
    Note that right child is pushed first so 
    that left is processed first */
        while (nodeStack.Count > 0) {

            // Pop the top item from stack and print it
            Node mynode = nodeStack.Peek();
            Console.Write(mynode.data + " ");
            nodeStack.Pop();

            // Push right and left children of
            // the popped node to stack
            if (mynode.right != null) {
                nodeStack.Push(mynode.right);
            }
            if (mynode.left != null) {
                nodeStack.Push(mynode.left);
            }
        }
    }

    // Driver Code
    public static void Main(string[] args)
    {
        GFG tree = new GFG();
        tree.root = new Node(10);
        tree.root.left = new Node(8);
        tree.root.right = new Node(2);
        tree.root.left.left = new Node(3);
        tree.root.left.right = new Node(5);
        tree.root.right.left = new Node(2);
        tree.iterativePreorder();
    }
}

// This code is contributed by Shrikant13
JavaScript 
 
// Javascript program to implement iterative
// preorder traversal

// A binary tree node
class Node
{
    constructor(item)
    {
        this.data = item;
        this.left = null;
        this.right = null;
    }
}

var root = null;

// An iterative process to print preorder
// traversal of Binary tree
function iterativePreorder(node)
{
    
    // Base Case
    if (node == null)
    {
        return;
    }
    
    // Create an empty stack and push root to it
    var nodeStack = [];
    nodeStack.push(root);
    
    /* Pop all items one by one. Do following
    for every popped item 
    a) print it 
    b) push its right child 
    c) push its left child 
    Note that right child is pushed first so 
    that left is processed first */
    while (nodeStack.length > 0)
    {
        
        // Pop the top item from stack and print it
        var mynode = nodeStack[nodeStack.length - 1];
        document.write(mynode.data + " ");
        nodeStack.pop();
        
        // Push right and left children of
        // the popped node to stack
        if (mynode.right != null) 
        {
            nodeStack.push(mynode.right);
        }
        if (mynode.left != null)
        {
            nodeStack.push(mynode.left);
        }
    }
}

// Driver Code
root = new Node(10);
root.left = new Node(8);
root.right = new Node(2);
root.left.left = new Node(3);
root.left.right = new Node(5);
root.right.left = new Node(2);

iterativePreorder(root);

// This code is contributed by itsok

Output
10 8 3 5 2 2

Time Complexity: O(N) 
Auxiliary Space: O(H), where H is the height of the tree.

Another Solution: In the previous solution we can see that the left child is popped as soon as it is pushed to the stack, therefore it is not required to push it into the stack. 

The idea is to start traversing the tree from the root node, and keep printing the left child while exists and simultaneously, push the right child of every node in an auxiliary stack. Once we reach a null node, pop a right child from the auxiliary stack and repeat the process while the auxiliary stack is not-empty. 

This is a micro-optimization over the previous approach, both the solutions use asymptotically similar auxiliary space.

Below is the implementation of the above approach: 

C++ 
#include <bits/stdc++.h>
using namespace std;

// Tree Node
struct Node {
    int data;
    Node *left, *right;

    Node(int data)
    {
        this->data = data;
        this->left = this->right = NULL;
    }
};

// Iterative function to do Preorder traversal of the tree
void preorderIterative(Node* root)
{
    if (root == NULL)
        return;

    stack<Node*> st;

    // start from root node (set current node to root node)
    Node* curr = root;

    // run till stack is not empty or current is
    // not NULL
    while (!st.empty() || curr != NULL) {
        // Print left children while exist
        // and keep pushing right into the
        // stack.
        while (curr != NULL) {
            cout << curr->data << " ";

            if (curr->right)
                st.push(curr->right);

            curr = curr->left;
        }

        // We reach when curr is NULL, so We
        // take out a right child from stack
        if (st.empty() == false) {
            curr = st.top();
            st.pop();
        }
    }
}

// Driver Code
int main()
{
    Node* root = new Node(10);
    root->left = new Node(20);
    root->right = new Node(30);
    root->left->left = new Node(40);
    root->left->left->left = new Node(70);
    root->left->right = new Node(50);
    root->right->left = new Node(60);
    root->left->left->right = new Node(80);

    preorderIterative(root);

    return 0;
}
Java 
import java.util.Stack;

// A binary tree node
class Node
{
    int data;
    Node left, right;

    Node(int item)
    {
        data = item;
        left = right = null;
    }
}

class BinaryTree{

Node root;

void preorderIterative()
{
    preorderIterative(root);
}

// Iterative function to do Preorder
// traversal of the tree 
void preorderIterative(Node node)
{
    if (node == null) 
    {
        return;
    }

    Stack<Node> st = new Stack<Node>();
    
    // Start from root node (set curr 
    // node to root node)
    Node curr = node;
    
    // Run till stack is not empty or 
    // current is not NULL 
    while (curr != null || !st.isEmpty())
    {
        
        // Print left children while exist 
        // and keep pushing right into the  
        // stack. 
        while (curr != null)
        {
            System.out.print(curr.data + " ");
            
            if (curr.right != null)
                st.push(curr.right);
                
            curr = curr.left;
        }
        
        // We reach when curr is NULL, so We 
        // take out a right child from stack 
        if (!st.isEmpty()) 
        {
            curr = st.pop();
        }
    }
}

// Driver code
public static void main(String args[])
{
    BinaryTree tree = new BinaryTree();
    
    tree.root = new Node(10);
    tree.root.left = new Node(20);
    tree.root.right = new Node(30);
    tree.root.left.left = new Node(40);
    tree.root.left.left.left = new Node(70);
    tree.root.left.right = new Node(50);
    tree.root.right.left = new Node(60);
    tree.root.left.left.right = new Node(80);
    
    tree.preorderIterative();
}
}

// This code is contributed by Vivek Singh Bhadauria
Python 
# Tree Node
class Node:

    def __init__(self, data = 0):
        self.data = data
        self.left = None
        self.right = None
    
# Iterative function to do Preorder traversal of the tree
def preorderIterative(root):

    if (root == None):
        return

    st = []

    # start from root node (set current node to root node)
    curr = root

    # run till stack is not empty or current is 
    # not NULL
    while (len(st) or curr != None):
    
        # Print left children while exist
        # and keep appending right into the 
        # stack.
        while (curr != None):
        
            print(curr.data, end = " ")

            if (curr.right != None):
                st.append(curr.right)

            curr = curr.left
        
        # We reach when curr is NULL, so We
        # take out a right child from stack
        if (len(st) > 0):
            curr = st[-1]
            st.pop()
            
# Driver Code

root = Node(10)
root.left = Node(20)
root.right = Node(30)
root.left.left = Node(40)
root.left.left.left = Node(70)
root.left.right = Node(50)
root.right.left = Node(60)
root.left.left.right = Node(80)

preorderIterative(root)

# This code is contributed by Arnab Kundu
C# 
using System;
using System.Collections.Generic;

// A binary tree node
public class Node
{
    public int data;
    public Node left, right;

    public Node(int item)
    {
        data = item;
        left = right = null;
    }
}

public class BinaryTree{

Node root;

void preorderIterative()
{
    preorderIterative(root);
}

// Iterative function to do Preorder
// traversal of the tree 
void preorderIterative(Node node)
{
    if (node == null) 
    {
        return;
    }

    Stack<Node> st = new Stack<Node>();
    
    // Start from root node (set curr 
    // node to root node)
    Node curr = node;
    
    // Run till stack is not empty or 
    // current is not NULL 
    while (curr != null || st.Count!=0)
    {
        
        // Print left children while exist 
        // and keep pushing right into the  
        // stack. 
        while (curr != null)
        {
            Console.Write(curr.data + " ");
            
            if (curr.right != null)
                st.Push(curr.right);
                
            curr = curr.left;
        }
        
        // We reach when curr is NULL, so We 
        // take out a right child from stack 
        if (st.Count != 0) 
        {
            curr = st.Pop();
        }
    }
}

// Driver code
public static void Main(String []args)
{
    BinaryTree tree = new BinaryTree();
    
    tree.root = new Node(10);
    tree.root.left = new Node(20);
    tree.root.right = new Node(30);
    tree.root.left.left = new Node(40);
    tree.root.left.left.left = new Node(70);
    tree.root.left.right = new Node(50);
    tree.root.right.left = new Node(60);
    tree.root.left.left.right = new Node(80);
    
    tree.preorderIterative();
}
}

// This code is contributed by Amit Katiyar
JavaScript 
class Node
{
    constructor(item) 
    {
        this.left = null;
        this.right = null;
        this.data = item;
    }
}

let root;

// Iterative function to do Preorder
// traversal of the tree
function preorderiterative(node)
{
    if (node == null)
    {
        return;
    }

    let st = [];

    // Start from root node (set curr
    // node to root node)
    let curr = node;

    // Run till stack is not empty or
    // current is not NULL
    while (curr != null || st.length > 0)
    {
        
        // Print left children while exist
        // and keep pushing right into the 
        // stack.
        while (curr != null)
        {
            document.write(curr.data + " ");

            if (curr.right != null)
                st.push(curr.right);

            curr = curr.left;
        }

        // We reach when curr is NULL, so We
        // take out a right child from stack
        if (st.length > 0)
        {
            curr = st.pop();
        }
    }
}

function preorderIterative()
{
    preorderiterative(root);
}

// Driver code
root = new Node(10);
root.left = new Node(20);
root.right = new Node(30);
root.left.left = new Node(40);
root.left.left.left = new Node(70);
root.left.right = new Node(50);
root.right.left = new Node(60);
root.left.left.right = new Node(80);
 
preorderIterative();

// This code is contributed by decode2207

Output
10 20 40 70 80 50 30 60

Time Complexity: O(N) 
Auxiliary Space: O(H), where H is the height of the tree.

ANOTHER APPROACH:

Intuition:

Using Morris Traversal, we can traverse the tree without using stack and recursion. The algorithm for Preorder is almost similar to Morris traversal for Inorder.

1…If left child is null, print the current node data. Move to right child. 
….Else, Make the right child of the inorder predecessor point to the current node. Two cases arise: 
………a) The right child of the inorder predecessor already points to the current node. Set right child to NULL. Move to right child of current node. 
………b) The right child is NULL. Set it to the current node. Print the current node’s data and move to left child of current node. 
2…Iterate until the current node is not NULL.

Implementation:

C++ 
// C++ code for this approach
#include <iostream>

using namespace std;

// A binary tree node
class Node {
public:
    int data;
    Node* left;
    Node* right;

    Node(int item) {
        data = item;
        left = right = NULL;
    }
};

class BinaryTree {
public:
    Node* root;

    void morrisTraversalPreorder() {
        morrisTraversalPreorder(root);
    }

    // Preorder traversal without recursion and without stack
    void morrisTraversalPreorder(Node* node) {
        while (node != NULL) {
            // If left child is null, print the current node data. Move to the right child.
            if (node->left == NULL) {
                cout << node->data << " ";
                node = node->right;
            } else {
                // Find the inorder predecessor
                Node* current = node->left;
                while (current->right != NULL && current->right != node) {
                    current = current->right;
                }

                // If the right child of the inorder predecessor already points to this node
                if (current->right == node) {
                    current->right = NULL;
                    node = node->right;
                } else {
                    cout << node->data << " ";
                    current->right = node;
                    node = node->left;
                }
            }
        }
    }

    void preorder() {
        preorder(root);
    }

    // Function for Standard preorder traversal
    void preorder(Node* node) {
        if (node != NULL) {
            cout << node->data << " ";
            preorder(node->left);
            preorder(node->right);
        }
    }
};

// Driver program to test the above functions
int main() {
    BinaryTree tree;
    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.root->right->left = new Node(6);
    tree.root->right->right = new Node(7);
    tree.root->left->left->left = new Node(8);
    tree.root->left->left->right = new Node(9);
    tree.root->left->right->left = new Node(10);
    tree.root->left->right->right = new Node(11);
    tree.morrisTraversalPreorder();
    cout << endl;
    tree.preorder();
    return 0;
}

// This code is contributed by guptapratik
Java 
// Java program to implement Morris preorder traversal

// A binary tree node
class Node {

    int data;
    Node left, right;

    Node(int item)
    {
        data = item;
        left = right = null;
    }
}

class BinaryTree {

    Node root;

    void morrisTraversalPreorder()
    {
        morrisTraversalPreorder(root);
    }

    // Preorder traversal without recursion and without
    // stack
    void morrisTraversalPreorder(Node node)
    {
        while (node != null) {

            // If left child is null, print the current node
            // data. Move to right child.
            if (node.left == null) {
                System.out.print(node.data + " ");
                node = node.right;
            }
            else {

                // Find inorder predecessor
                Node current = node.left;
                while (current.right != null
                       && current.right != node) {
                    current = current.right;
                }

                // If the right child of inorder predecessor
                // already points to this node
                if (current.right == node) {
                    current.right = null;
                    node = node.right;
                }

                // If right child doesn't point to this
                // node, then print this node and make right
                // child point to this node
                else {
                    System.out.print(node.data + " ");
                    current.right = node;
                    node = node.left;
                }
            }
        }
    }

    void preorder() { preorder(root); }

    // Function for Standard preorder traversal
    void preorder(Node node)
    {
        if (node != null) {
            System.out.print(node.data + " ");
            preorder(node.left);
            preorder(node.right);
        }
    }

    // Driver programs to test above functions
    public static void main(String args[])
    {
        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.root.right.left = new Node(6);
        tree.root.right.right = new Node(7);
        tree.root.left.left.left = new Node(8);
        tree.root.left.left.right = new Node(9);
        tree.root.left.right.left = new Node(10);
        tree.root.left.right.right = new Node(11);
        tree.morrisTraversalPreorder();
        System.out.println("");
        tree.preorder();
    }
}

// this code has been contributed by Raunak Singh
Python 
# Python3 program to implement Morris preorder traversal

# A binary tree node

class Node:
    def __init__(self, item):
        self.data = item
        self.left = self.right = None

class BinaryTree:
    def __init__(self):
        self.root = None

    def morris_traversal_preorder(self):
        self.morris_traversal_preorder_helper(self.root)

    # Preorder traversal without recursion and without stack
    def morris_traversal_preorder_helper(self, node):
        while node:
            # If left child is None, print the current 
            # node data. Move to the right child.
            if node.left is None:
                print(node.data, end=" ")
                node = node.right
            else:
                # Find inorder predecessor
                current = node.left
                while current.right is not None and current.right is not node:
                    current = current.right

                # If the right child of the inorder 
                # predecessor already points to this node
                if current.right is node:
                    current.right = None
                    node = node.right
                else:
                    # If the right child doesn't point to this node, 
                    # then print this node
                    # and make the right child point to this node
                    print(node.data, end=" ")
                    current.right = node
                    node = node.left

    def preorder(self):
        self.preorder_helper(self.root)

    # Function for standard preorder traversal
    def preorder_helper(self, node):
        if node is not None:
            print(node.data, end=" ")
            self.preorder_helper(node.left)
            self.preorder_helper(node.right)

# Driver program to test the above functions
tree = BinaryTree()
tree.root = Node(1)
tree.root.left = Node(2)
tree.root.right = Node(3)
tree.root.left.left = Node(4)
tree.root.left.right = Node(5)
tree.root.right.left = Node(6)
tree.root.right.right = Node(7)
tree.root.left.left.left = Node(8)
tree.root.left.left.right = Node(9)
tree.root.left.right.left = Node(10)
tree.root.left.right.right = Node(11)

tree.morris_traversal_preorder()
print("")
tree.preorder()
C# 
using System;

// A binary tree node
class Node
{
    public int data;
    public Node left, right;

    public Node(int item)
    {
        data = item;
        left = right = null;
    }
}

class BinaryTree
{
    public Node root;

    public void morrisTraversalPreorder()
    {
        morrisTraversalPreorder(root);
    }

    // Preorder traversal without recursion and without
    // stack
    public void morrisTraversalPreorder(Node node)
    {
        while (node != null)
        {
            // If left child is null, print the current node
            // data. Move to right child.
            if (node.left == null)
            {
                Console.Write(node.data + " ");
                node = node.right;
            }
            else
            {
                // Find inorder predecessor
                Node current = node.left;
                while (current.right != null
                       && current.right != node)
                {
                    current = current.right;
                }

                // If the right child of the inorder predecessor
                // already points to this node
                if (current.right == node)
                {
                    current.right = null;
                    node = node.right;
                }
                // If the right child doesn't point to this
                // node, then print this node and make the right
                // child point to this node
                else
                {
                    Console.Write(node.data + " ");
                    current.right = node;
                    node = node.left;
                }
            }
        }
    }

    public void Preorder()
    {
        Preorder(root);
    }

    // Function for Standard preorder traversal
    public void Preorder(Node node)
    {
        if (node != null)
        {
            Console.Write(node.data + " ");
            Preorder(node.left);
            Preorder(node.right);
        }
    }

    // Driver programs to test the above functions
    public static void Main(string[] args)
    {
        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.root.right.left = new Node(6);
        tree.root.right.right = new Node(7);
        tree.root.left.left.left = new Node(8);
        tree.root.left.left.right = new Node(9);
        tree.root.left.right.left = new Node(10);
        tree.root.left.right.right = new Node(11);
        tree.morrisTraversalPreorder();
        Console.WriteLine();
        tree.Preorder();
    }
}

// This code has been contributed by phasing17
JavaScript 
class Node {
    constructor(item) {
        this.data = item;
        this.left = this.right = null;
    }
}

class BinaryTree {
    constructor() {
        this.root = null;
    }

    morrisTraversalPreorder() {
        this.morrisTraversalPreorderHelper(this.root);
    }

    // Preorder traversal without recursion and without stack
    morrisTraversalPreorderHelper(node) {
        while (node) {
            // If left child is null, print the current node data. Move to right child.
            if (node.left === null) {
                process.stdout.write(node.data + " ");
                node = node.right;
            } else {
                // Find inorder predecessor
                let current = node.left;
                while (current.right !== null && current.right !== node) {
                    current = current.right;
                }

                // If the right child of inorder predecessor already points to this node
                if (current.right === node) {
                    current.right = null;
                    node = node.right;
                } else {
                    // If right child doesn't point to this node, then print this node
                    // and make right child point to this node
                    process.stdout.write(node.data + " ");
                    current.right = node;
                    node = node.left;
                }
            }
        }
    }

    preorder() {
        this.preorderHelper(this.root);
    }

    // Function for Standard preorder traversal
    preorderHelper(node) {
        if (node !== null) {
            process.stdout.write(node.data + " ");
            this.preorderHelper(node.left);
            this.preorderHelper(node.right);
        }
    }
}

// Driver program to test above functions
const 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.root.right.left = new Node(6);
tree.root.right.right = new Node(7);
tree.root.left.left.left = new Node(8);
tree.root.left.left.right = new Node(9);
tree.root.left.right.left = new Node(10);
tree.root.left.right.right = new Node(11);
tree.morrisTraversalPreorder();
console.log("");
tree.preorder();

Output
1 2 4 8 9 5 10 11 3 6 7 
1 2 4 8 9 5 10 11 3 6 7

Time Complexity: O(n), we visit every node at most once.
Auxiliary Space: O(1), we use a constant amount of space for variables and pointers.



Next Article
Iterative Postorder Traversal | Set 1 (Using Two Stacks)
author
kartik
News
Improve

Similar Reads

Article Tags :
Practice Tags :
three90RightbarBannerImg
We use cookies to ensure you have the best browsing experience on our website. By using our site, you acknowledge that you have read and understood our Cookie Policy & Privacy Policy
Lightbox
  翻译：