Open In App

Iterative Preorder Traversal

Last Updated : 22 May, 2024
Improve
Improve
Like Article
Like
Save
Share
Report

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.



https://media.geeksforgeeks.org/auth/avatar.png
GeeksforGeeks
Improve
Previous Article
Morris traversal for Preorder
Next Article
Iterative Postorder Traversal | Set 1 (Using Two Stacks)

Similar Reads

Construct Full Binary Tree using its Preorder traversal and Preorder traversal of its mirror tree
Given two arrays that represent Preorder traversals of a full binary tree and its mirror tree, we need to write a program to construct the binary tree using these two Preorder traversals.A Full Binary Tree is a binary tree where every node has either 0 or 2 children. Note: It is not possible to construct a general binary tree using these two traver
12 min read
Check if a binary tree is subtree of another binary tree using preorder traversal : Iterative
Given two binary trees S and T, the task is the check that if S is a subtree of the Tree T. For Example: Input: Tree T - 1 / \ 2 3 / \ / \ 4 5 6 7 Tree S - 2 / \ 4 5 Output: YES Explanation: The above tree is the subtree of the tree T, Hence the output is YES Approach: The idea is to traverse both the tree in Pre-order Traversal and check for each
11 min read
Find postorder traversal of BST from preorder traversal
Given an array representing preorder traversal of BST, print its postorder traversal. Examples: Input : 40 30 35 80 100 Output : 35 30 100 80 40 Input : 40 30 32 35 80 90 100 120 Output : 35 32 30 120 100 90 80 40 Prerequisite: Construct BST from given preorder traversal Simple Approach: A simple solution is to first construct BST from a given preo
9 min read
Construct BST from given preorder traversal using Stack
Given preorder traversal of a binary search tree, construct the BST.For example, if the given traversal is {10, 5, 1, 7, 40, 50}, then the output should be root of following tree. 10 / \ 5 40 / \ \ 1 7 50 We have discussed O(n^2) and O(n) recursive solutions in the previous post. Following is a stack based iterative solution that works in O(n) time
13 min read
Modify a binary tree to get preorder traversal using right pointers only
Given a binary tree. Modify it in such a way that after modification you can have a preorder traversal of it using only the right pointers. During modification, you can use right as well as left pointers. Examples: Input : 10 / \ 8 2 / \ 3 5 Output : 10 \ 8 \ 3 \ 5 \ 2 Explanation : The preorder traversal of given binary tree is 10 8 3 5 2. Method
15 min read
Find n-th node in Preorder traversal of a Binary Tree
Given a Binary tree and a number N, write a program to find the N-th node in the Preorder traversal of the given Binary tree. Prerequisite: Tree Traversal Examples: Input: N = 4 11 / \ 21 31 / \ 41 51 Output: 51 Explanation: Preorder Traversal of given Binary Tree is 11 21 41 51 31, so 4th node will be 51. Input: N = 5 25 / \ 20 30 / \ / \ 18 22 24
6 min read
Number of elements smaller than root using preorder traversal of a BST
Given a preorder traversal of a BST. The task is to find the number of elements less than root. Examples: Input: preorder[] = {3, 2, 1, 0, 5, 4, 6} Output: 3 Input: preorder[] = {5, 4, 3, 2, 1} Output: 4 For a binary search tree, a preorder traversal is of the form: root, { elements in left subtree of root }, { elements in right subtree of root } S
9 min read
Preorder Traversal of an N-ary Tree
Given an N-ary Tree. The task is to write a program to perform the preorder traversal of the given n-ary tree. Examples: Input: 3-Array Tree 1 / | \ / | \ 2 3 4 / \ / | \ 5 6 7 8 9 / / | \ 10 11 12 13 Output: 1 2 5 10 6 11 12 13 3 4 7 8 9 Input: 3-Array Tree 1 / | \ / | \ 2 3 4 / \ / | \ 5 6 7 8 9 Output: 1 2 5 6 3 4 7 8 9 The preorder Traversal of
14 min read
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
7 min read
Find Leftmost and Rightmost node of BST from its given preorder traversal
Given a preorder sequence of the binary search tree of N nodes. The task is to find its leftmost and rightmost nodes. Examples: Input : N = 5, preorder[]={ 3, 2, 1, 5, 4 } Output : Leftmost = 1, Rightmost = 5 The BST constructed from this preorder sequence would be: 3 / \ 2 5 / / 1 4 Leftmost Node of this tree is equal to 1 Rightmost Node of this t
5 min read
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