# Preorder Tree Traversal of a Binary Tree

That is another form of preorder tree traversal of a binary tree. We can solve this problem in a two way using recursion and iterative.

## Recursive approach

1) When current node are not NULL then print that element value. After that visit left child of this current node. when visited node is not NULL then repeat this step. Otherwise do step 2.

2) Visit the right subtree of current node, if this is not NULL then execute step 1.

Here given code implementation process.

``````/*
Java Program
Preorder Tree Traversal of a Binary Tree
using recursion
*/
// Binary Tree node
class TreeNode
{
public int data;
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
class BinaryTree
{
public TreeNode root;
public BinaryTree()
{
// Set initial tree root
this.root = null;
}
// Display preorder view of binary tree
public void preorder(TreeNode node)
{
if (node != null)
{
// Print node value
System.out.print("  " + node.data);
// Visit left subtree
preorder(node.left);
// Visit right subtree
preorder(node.right);
}
}
public static void main(String[] args)
{
// Create new tree
BinaryTree tree = new BinaryTree();
/*
Binary Tree
-------------
17
/    \
11      21
/ \     /  \
1   39  10   2
/
40
*/
tree.root = new TreeNode(17);
tree.root.left = new TreeNode(11);
tree.root.right = new TreeNode(21);
tree.root.right.right = new TreeNode(2);
tree.root.right.left = new TreeNode(10);
tree.root.left.left = new TreeNode(1);
tree.root.left.right = new TreeNode(39);
tree.root.left.right.left = new TreeNode(40);
// Display Tree Node
tree.preorder(tree.root);
}
}``````

#### Output

``  17  11  1  39  40  21  10  2``
``````/*
C Program for
Preorder Tree Traversal of a Binary Tree
using Recusion
*/
#include <stdio.h>
#include <stdlib.h>

// Binary Tree node
struct TreeNode
{
int data;
struct TreeNode *left, *right;
};
// Binary Tree
struct BinaryTree
{
struct TreeNode *root;
};
// Create new tree
struct BinaryTree *newTree()
{
// Create dynamic node
struct BinaryTree *tree =
(struct BinaryTree *) malloc(sizeof(struct BinaryTree));
if (tree != NULL)
{
tree->root = NULL;
}
else
{
printf("Memory Overflow to Create tree Tree\n");
}
// Return new tree
return tree;
}
// This is creating a binary tree node and return this
struct TreeNode *getNode(int data)
{
// Create dynamic node
struct TreeNode *node =
(struct TreeNode *) malloc(sizeof(struct TreeNode));
if (node != NULL)
{
// Set data and pointer values
node->data = data;
node->left = NULL;
node->right = NULL;
}
else
{
// This is indicates, segmentation fault or
// Memory overflow problem
printf("Memory Overflow\n");
}
// Return new node
return node;
}
// Recursive function
// Display preorder view of binary tree
void preorder(struct TreeNode *node)
{
if (node != NULL)
{
// Print node value
printf("  %d", node->data);
preorder(node->left);
preorder(node->right);
}
}
int main()
{
struct BinaryTree *tree = newTree();
/*
Binary Tree
-------------
17
/    \
11      21
/ \     /  \
1   39  10   2
/
40
*/
tree->root = getNode(17);
tree->root->left = getNode(11);
tree->root->right = getNode(21);
tree->root->right->right = getNode(2);
tree->root->right->left = getNode(10);
tree->root->left->left = getNode(1);
tree->root->left->right = getNode(39);
tree->root->left->right->left = getNode(40);
// Display tree node
preorder(tree->root);
return 0;
}``````

#### Output

``  17  11  1  39  40  21  10  2``
``````// Include header file
#include <iostream>
using namespace std;
/*
C++ Program
Preorder Tree Traversal of a Binary Tree
using recursion
*/
// Binary Tree node
class TreeNode
{
public: int data;
TreeNode *left;
TreeNode *right;
TreeNode(int data)
{
// Set node value
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
class BinaryTree
{
public: TreeNode *root;
BinaryTree()
{
this->root = NULL;
}
// Display preorder view of binary tree
void preorder(TreeNode *node)
{
if (node != NULL)
{
// Print node value
cout << "  " << node->data;
// Visit left subtree
this->preorder(node->left);
// Visit right subtree
this->preorder(node->right);
}
}
};
int main()
{
// Create new tree
BinaryTree *tree = new BinaryTree();
/*
Binary Tree
-------------
17
/    \
11      21
/ \     /  \
1   39  10   2
/
40
*/
tree->root = new TreeNode(17);
tree->root->left = new TreeNode(11);
tree->root->right = new TreeNode(21);
tree->root->right->right = new TreeNode(2);
tree->root->right->left = new TreeNode(10);
tree->root->left->left = new TreeNode(1);
tree->root->left->right = new TreeNode(39);
tree->root->left->right->left = new TreeNode(40);
// Display Tree Node
tree->preorder(tree->root);
return 0;
}``````

#### Output

``  17  11  1  39  40  21  10  2``
``````package main
import "fmt"
/*
Go Program
Preorder Tree Traversal of a Binary Tree
using recursion
*/
// Binary Tree node
type TreeNode struct {
data int
left * TreeNode
right * TreeNode
}
func getTreeNode(data int) * TreeNode {
var me *TreeNode = &TreeNode {}
// Set node value
me.data = data
me.left = nil
me.right = nil
return me
}
type BinaryTree struct {
root * TreeNode
}
func getBinaryTree() * BinaryTree {
var me *BinaryTree = &BinaryTree {}
// Set initial tree root
me.root = nil
return me
}
// Display preorder view of binary tree
func(this BinaryTree) preorder(node * TreeNode) {
if node != nil {
// Print node value
fmt.Print("  ", node.data)
// Visit left subtree
this.preorder(node.left)
// Visit right subtree
this.preorder(node.right)
}
}
func main() {
// Create new tree
var tree * BinaryTree = getBinaryTree()
/*
Binary Tree
-------------
17
/    \
11      21
/ \     /  \
1   39  10   2
/
40
*/
tree.root = getTreeNode(17)
tree.root.left = getTreeNode(11)
tree.root.right = getTreeNode(21)
tree.root.right.right = getTreeNode(2)
tree.root.right.left = getTreeNode(10)
tree.root.left.left = getTreeNode(1)
tree.root.left.right = getTreeNode(39)
tree.root.left.right.left = getTreeNode(40)
// Display Tree Node
tree.preorder(tree.root)
}``````

#### Output

``  17  11  1  39  40  21  10  2``
``````// Include namespace system
using System;
/*
Csharp Program
Preorder Tree Traversal of a Binary Tree
using recursion
*/
// Binary Tree node
public class TreeNode
{
public int data;
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
public class BinaryTree
{
public TreeNode root;
public BinaryTree()
{
// Set initial tree root
this.root = null;
}
// Display preorder view of binary tree
public void preorder(TreeNode node)
{
if (node != null)
{
// Print node value
Console.Write("  " + node.data);
// Visit left subtree
this.preorder(node.left);
// Visit right subtree
this.preorder(node.right);
}
}
public static void Main(String[] args)
{
// Create new tree
BinaryTree tree = new BinaryTree();
/*
Binary Tree
-------------
17
/    \
11      21
/ \     /  \
1   39  10   2
/
40
*/
tree.root = new TreeNode(17);
tree.root.left = new TreeNode(11);
tree.root.right = new TreeNode(21);
tree.root.right.right = new TreeNode(2);
tree.root.right.left = new TreeNode(10);
tree.root.left.left = new TreeNode(1);
tree.root.left.right = new TreeNode(39);
tree.root.left.right.left = new TreeNode(40);
// Display Tree Node
tree.preorder(tree.root);
}
}``````

#### Output

``  17  11  1  39  40  21  10  2``
``````<?php
/*
Php Program
Preorder Tree Traversal of a Binary Tree
using recursion
*/
// Binary Tree node
class TreeNode
{
public \$data;
public \$left;
public \$right;
public  function __construct(\$data)
{
// Set node value
\$this->data = \$data;
\$this->left = NULL;
\$this->right = NULL;
}
}
class BinaryTree
{
public \$root;
public  function __construct()
{
\$this->root = NULL;
}
// Display preorder view of binary tree
public  function preorder(\$node)
{
if (\$node != NULL)
{
// Print node value
echo("  ".\$node->data);
// Visit left subtree
\$this->preorder(\$node->left);
// Visit right subtree
\$this->preorder(\$node->right);
}
}
}

function main()
{
// Create new tree
\$tree = new BinaryTree();
/*
Binary Tree
-------------
17
/    \
11      21
/ \     /  \
1   39  10   2
/
40
*/
\$tree->root = new TreeNode(17);
\$tree->root->left = new TreeNode(11);
\$tree->root->right = new TreeNode(21);
\$tree->root->right->right = new TreeNode(2);
\$tree->root->right->left = new TreeNode(10);
\$tree->root->left->left = new TreeNode(1);
\$tree->root->left->right = new TreeNode(39);
\$tree->root->left->right->left = new TreeNode(40);
// Display Tree Node
\$tree->preorder(\$tree->root);
}
main();``````

#### Output

``  17  11  1  39  40  21  10  2``
``````/*
Node JS Program
Preorder Tree Traversal of a Binary Tree
using recursion
*/
// Binary Tree node
class TreeNode
{
constructor(data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
class BinaryTree
{
constructor()
{
this.root = null;
}
// Display preorder view of binary tree
preorder(node)
{
if (node != null)
{
// Print node value
process.stdout.write("  " + node.data);
// Visit left subtree
this.preorder(node.left);
// Visit right subtree
this.preorder(node.right);
}
}
}

function main()
{
// Create new tree
var tree = new BinaryTree();
/*
Binary Tree
-------------
17
/    \
11      21
/ \     /  \
1   39  10   2
/
40
*/
tree.root = new TreeNode(17);
tree.root.left = new TreeNode(11);
tree.root.right = new TreeNode(21);
tree.root.right.right = new TreeNode(2);
tree.root.right.left = new TreeNode(10);
tree.root.left.left = new TreeNode(1);
tree.root.left.right = new TreeNode(39);
tree.root.left.right.left = new TreeNode(40);
// Display Tree Node
tree.preorder(tree.root);
}
main();``````

#### Output

``  17  11  1  39  40  21  10  2``
``````#  Python 3 Program
#  Preorder Tree Traversal of a Binary Tree
#  using recursion

#  Binary Tree node
class TreeNode :
def __init__(self, data) :
#  Set node value
self.data = data
self.left = None
self.right = None

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

#  Display preorder view of binary tree
def preorder(self, node) :
if (node != None) :
#  Print node value
print("  ", node.data, end = "")
#  Visit left subtree
self.preorder(node.left)
#  Visit right subtree
self.preorder(node.right)

def main() :
#  Create new tree
tree = BinaryTree()
#    Binary Tree
#    -------------
#          17
#        /    \
#      11      21
#     / \     /  \
#    1   39  10   2
#       /
#      40
tree.root = TreeNode(17)
tree.root.left = TreeNode(11)
tree.root.right = TreeNode(21)
tree.root.right.right = TreeNode(2)
tree.root.right.left = TreeNode(10)
tree.root.left.left = TreeNode(1)
tree.root.left.right = TreeNode(39)
tree.root.left.right.left = TreeNode(40)
#  Display Tree Node
tree.preorder(tree.root)

if __name__ == "__main__": main()``````

#### Output

``   17   11   1   39   40   21   10   2``
``````#  Ruby Program
#  Preorder Tree Traversal of a Binary Tree
#  using recursion

#  Binary Tree node
class TreeNode
# Define the accessor and reader of class TreeNode
attr_accessor :data, :left, :right
def initialize(data)
#  Set node value
self.data = data
self.left = nil
self.right = nil
end

end

class BinaryTree
# Define the accessor and reader of class BinaryTree
attr_accessor :root
def initialize()
self.root = nil
end

#  Display preorder view of binary tree
def preorder(node)
if (node != nil)
#  Print node value
print("  ", node.data)
#  Visit left subtree
self.preorder(node.left)
#  Visit right subtree
self.preorder(node.right)
end

end

end

def main()
#  Create new tree
tree = BinaryTree.new()
#    Binary Tree
#    -------------
#          17
#        /    \
#      11      21
#     / \     /  \
#    1   39  10   2
#       /
#      40
tree.root = TreeNode.new(17)
tree.root.left = TreeNode.new(11)
tree.root.right = TreeNode.new(21)
tree.root.right.right = TreeNode.new(2)
tree.root.right.left = TreeNode.new(10)
tree.root.left.left = TreeNode.new(1)
tree.root.left.right = TreeNode.new(39)
tree.root.left.right.left = TreeNode.new(40)
#  Display Tree Node
tree.preorder(tree.root)
end

main()``````

#### Output

``  17  11  1  39  40  21  10  2``
``````/*
Scala Program
Preorder Tree Traversal of a Binary Tree
using recursion
*/
// Binary Tree node
class TreeNode(var data: Int,
var left: TreeNode,
var right: TreeNode)
{
def this(data: Int)
{
// Set node value
this(data, null, null);
}
}
class BinaryTree(var root: TreeNode)
{
def this()
{

this(null);
}
// Display preorder view of binary tree
def preorder(node: TreeNode): Unit = {
if (node != null)
{
// Print node value
print("  " + node.data);
// Visit left subtree
preorder(node.left);
// Visit right subtree
preorder(node.right);
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
// Create new tree
var tree: BinaryTree = new BinaryTree();
/*
Binary Tree
-------------
17
/    \
11      21
/ \     /  \
1   39  10   2
/
40
*/
tree.root = new TreeNode(17);
tree.root.left = new TreeNode(11);
tree.root.right = new TreeNode(21);
tree.root.right.right = new TreeNode(2);
tree.root.right.left = new TreeNode(10);
tree.root.left.left = new TreeNode(1);
tree.root.left.right = new TreeNode(39);
tree.root.left.right.left = new TreeNode(40);
// Display Tree Node
tree.preorder(tree.root);
}
}``````

#### Output

``  17  11  1  39  40  21  10  2``
``````/*
Swift 4 Program
Preorder Tree Traversal of a Binary Tree
using recursion
*/
// Binary Tree node
class TreeNode
{
var data: Int;
var left: TreeNode? ;
var right: TreeNode? ;
init(_ data: Int)
{
// Set node value
self.data = data;
self.left = nil;
self.right = nil;
}
}
class BinaryTree
{
var root: TreeNode? ;
init()
{
self.root = nil;
}
// Display preorder view of binary tree
func preorder(_ node: TreeNode? )
{
if (node  != nil)
{
// Print node value
print("  ", node!.data, terminator: "");
// Visit left subtree
self.preorder(node!.left);
// Visit right subtree
self.preorder(node!.right);
}
}
}
func main()
{
// Create new tree
let tree: BinaryTree = BinaryTree();
/*
Binary Tree
-------------
17
/    \
11      21
/ \     /  \
1   39  10   2
/
40
*/
tree.root = TreeNode(17);
tree.root!.left = TreeNode(11);
tree.root!.right = TreeNode(21);
tree.root!.right!.right = TreeNode(2);
tree.root!.right!.left = TreeNode(10);
tree.root!.left!.left = TreeNode(1);
tree.root!.left!.right = TreeNode(39);
tree.root!.left!.right!.left = TreeNode(40);
// Display Tree Node
tree.preorder(tree.root);
}
main();``````

#### Output

``   17   11   1   39   40   21   10   2``
``````/*
Kotlin Program
Preorder Tree Traversal of a Binary Tree
using recursion
*/
// Binary Tree node
class TreeNode
{
var data: Int;
var left: TreeNode ? ;
var right: TreeNode ? ;
constructor(data: Int)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
class BinaryTree
{
var root: TreeNode ? ;
constructor()
{
this.root = null;
}
// Display preorder view of binary tree
fun preorder(node: TreeNode ? ): Unit
{
if (node != null)
{
// Print node value
print("  " + node.data);
// Visit left subtree
this.preorder(node.left);
// Visit right subtree
this.preorder(node.right);
}
}
}
fun main(args: Array < String > ): Unit
{
// Create new tree
val tree: BinaryTree = BinaryTree();
/*
Binary Tree
-------------
17
/    \
11      21
/ \     /  \
1   39  10   2
/
40
*/
tree.root = TreeNode(17);
tree.root?.left = TreeNode(11);
tree.root?.right = TreeNode(21);
tree.root?.right?.right = TreeNode(2);
tree.root?.right?.left = TreeNode(10);
tree.root?.left?.left = TreeNode(1);
tree.root?.left?.right = TreeNode(39);
tree.root?.left?.right?.left = TreeNode(40);
// Display Tree Node
tree.preorder(tree.root);
}``````

#### Output

``  17  11  1  39  40  21  10  2``

## Iterative approach

When we are need to traverse tree preorder form. Then we can used stack data structure to solve this problem.

``````/*
C Program
Preorder Tree Traversal of a Binary Tree
Using Stack
*/
#include <stdio.h>
#include <stdlib.h>

// Binary Tree node
struct TreeNode
{
int data;
struct TreeNode *left, *right;
};
// Binary Tree
struct BinaryTree
{
struct TreeNode *root;
};
// Stack Node
struct StackNode
{
struct TreeNode *element;
struct StackNode *next;
};
// Define a custom stack
struct MyStack
{
struct StackNode *top;
int size;
};
struct MyStack *newStack()
{
// Make a stack
struct MyStack *stack = (struct MyStack *) malloc(sizeof(struct MyStack));
if (stack != NULL)
{
// Set node values
stack->top = NULL;
stack->size = 0;
}
else
{
printf("\nMemory overflow when create new stack\n");
}
return stack;
}
// Returns the status of empty or non empty stacks
int isEmpty(struct MyStack *stack)
{
if (stack->size > 0 && stack->top != NULL)
{
return 0;
}
else
{
return 1;
}
}
// Add node at the top of stack
void push(struct MyStack *stack, struct TreeNode *element)
{
// Make a new node
struct StackNode *node =
(struct StackNode *) malloc(sizeof(struct StackNode));
if (node == NULL)
{
printf("\nMemory overflow when create new stack Node \n");
}
else
{
node->element = element;
node->next = stack->top;
}
stack->top = node;
stack->size++;
}
struct TreeNode *peek(struct MyStack *stack)
{
if (stack == NULL)
{
return NULL;
}
return stack->top->element;
}
// Remove top element of stack
void pop(struct MyStack *stack)
{
if (!isEmpty(stack))
{
struct StackNode *temp = stack->top;
// Change top element of stack
stack->top = temp->next;
// remove previous top
free(temp);
temp = NULL;
stack->size--;
}
}
// Create new tree
struct BinaryTree *newTree()
{
// Create dynamic node
struct BinaryTree *tree =
(struct BinaryTree *) malloc(sizeof(struct BinaryTree));
if (tree != NULL)
{
tree->root = NULL;
}
else
{
printf("Memory Overflow to Create tree Tree\n");
}
// Return new tree
return tree;
}
// This is creating a binary tree node and return this
struct TreeNode *getNode(int data)
{
// Create dynamic node
struct TreeNode *node =
(struct TreeNode *) malloc(sizeof(struct TreeNode));
if (node != NULL)
{
// Set data and pointer values
node->data = data;
node->left = NULL;
node->right = NULL;
}
else
{
// This is indicates, segmentation fault or
// Memory overflow problem
printf("Memory Overflow\n");
}
// Return new node
return node;
}
// Display preorder view of binary tree
void preorder(struct TreeNode *root)
{
if (root != NULL)
{
// Make new stack
struct MyStack *s = newStack();
struct TreeNode *node = root;
// Display tree element
while (!isEmpty(s) || node != NULL)
{
if (node != NULL)
{
// Display node value
printf("%d  ", node->data);
push(s, node);
// Visit to left subtree
node = node->left;
}
else
{
// When node is null
// Get stack top element
node = peek(s);

// Remove top element of the stack
pop(s);
// Visit to left subtree of current node
node = node->right;
}
}
}
else
{
}
}
int main()
{
struct BinaryTree *tree = newTree();
/*
Binary Tree
-------------
17
/    \
11      21
/ \     /  \
1   39  10   2
/
40
*/
tree->root = getNode(17);
tree->root->left = getNode(11);
tree->root->right = getNode(21);
tree->root->right->right = getNode(2);
tree->root->right->left = getNode(10);
tree->root->left->left = getNode(1);
tree->root->left->right = getNode(39);
tree->root->left->right->left = getNode(40);
// Display Tree elements
preorder(tree->root);
return 0;
}``````

#### Output

``17  11  1  39  40  21  10  2``
``````// Java Program
// Preorder traversal without recursion
// Using stack

// Binary Tree node
class TreeNode
{
public int data;
public TreeNode left;
public TreeNode right;
// Make a tree node
public TreeNode(int data)
{
// Set node data
this.data = data;
this.left = null;
this.right = null;
}
}
class StackNode
{
public TreeNode element;
public StackNode next;
public StackNode(TreeNode element)
{
this.element = element;
this.next = null;
}
}
// Stack Class
class MyStack
{
public StackNode top;
public int size;
public MyStack()
{
this.top = null;
this.size = 0;
}
// Add new element into stack
public void push(TreeNode element)
{
// Create new node
StackNode node = new StackNode(element);
node.next = this.top;
// new node is new top
this.top = node;
// Increase the size
this.size += 1;
}
// Remove top element of the stack
public void pop()
{
if (this.top != null)
{
// next node is new top
this.top = this.top.next;
// Reduce size
this.size -= 1;
}
}
// Returns the status of empty or non empty stacks
public boolean isEmpty()
{
if (this.size > 0 && this.top != null)
{
return false;
}
else
{
return true;
}
}
public TreeNode peek()
{
if (isEmpty())
{
return null;
}
return this.top.element;
}
}
public class BinaryTree
{
public TreeNode root;
public BinaryTree()
{
// Set initial tree root to null
this.root = null;
}
// Display preorder view of binary tree
public void preorder()
{
if (this.root != null)
{
// Make new stack
MyStack s = new MyStack();
TreeNode node = this.root;
// Display tree element
while (!s.isEmpty() || node != null)
{
if (node != null)
{
// Display node value
System.out.print(" " + node.data);
s.push(node);
// Visit to left subtree
node = node.left;
}
else
{
// When node is null
// Get stack top element
node = s.peek();
// Remove top element of the stack
s.pop();
// Visit to left subtree of current node
node = node.right;
}
}
}
else
{
}
}
public static void main(String[] args)
{
// Create new tree
BinaryTree tree = new BinaryTree();
/*
Binary Tree
-------------
17
/    \
11      21
/ \     /  \
1   39  10   2
/
40
*/
tree.root = new TreeNode(17);
tree.root.left = new TreeNode(11);
tree.root.right = new TreeNode(21);
tree.root.right.right = new TreeNode(2);
tree.root.right.left = new TreeNode(10);
tree.root.left.left = new TreeNode(1);
tree.root.left.right = new TreeNode(39);
tree.root.left.right.left = new TreeNode(40);
// Display Tree Node
tree.preorder();
}
}``````

#### Output

`` 17 11 1 39 40 21 10 2``
``````// Include header file
#include <iostream>
using namespace std;
// C++ Program
// Preorder traversal without recursion
// Using stack

// Binary Tree node
class TreeNode
{
public: int data;
TreeNode *left;
TreeNode *right;
// Make a tree node
TreeNode(int data)
{
// Set node data
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
class StackNode
{
public: TreeNode *element;
StackNode *next;
StackNode(TreeNode *element)
{
this->element = element;
this->next = NULL;
}
};
// Stack Class
class MyStack
{
public: StackNode *top;
int size;
MyStack()
{
this->top = NULL;
this->size = 0;
}
// Add new element into stack
void push(TreeNode *element)
{
// Create new node
StackNode *node = new StackNode(element);
node->next = this->top;
// new node is new top
this->top = node;
// Increase the size
this->size += 1;
}
// Remove top element of the stack
void pop()
{
if (this->top != NULL)
{
struct StackNode *temp = this->top;
// next node is new top
this->top = this->top->next;
// Reduce size
this->size -= 1;
// Free memory
delete temp;
}
}
// Returns the status of empty or non empty stacks
bool isEmpty()
{
if (this->size > 0 && this->top != NULL)
{
return false;
}
else
{
return true;
}
}
TreeNode *peek()
{
if (this->isEmpty())
{
return NULL;
}
return this->top->element;
}
};
class BinaryTree
{
public: TreeNode *root;
BinaryTree()
{
this->root = NULL;
}
// Display preorder view of binary tree
void preorder()
{
if (this->root != NULL)
{
// Make new stack
MyStack *s = new MyStack();
TreeNode *node = this->root;
// Display tree element
while (!s->isEmpty() || node != NULL)
{
if (node != NULL)
{
// Display node value
cout << " " << node->data;
s->push(node);
// Visit to left subtree
node = node->left;
}
else
{
// When node is null
// Get stack top element
node = s->peek();
// Remove top element of the stack
s->pop();
// Visit to left subtree of current node
node = node->right;
}
}
}
else
{
}
}
};
int main()
{
// Create new tree
BinaryTree *tree = new BinaryTree();
/*
Binary Tree
-------------
17
/    \
11      21
/ \     /  \
1   39  10   2
/
40
*/
tree->root = new TreeNode(17);
tree->root->left = new TreeNode(11);
tree->root->right = new TreeNode(21);
tree->root->right->right = new TreeNode(2);
tree->root->right->left = new TreeNode(10);
tree->root->left->left = new TreeNode(1);
tree->root->left->right = new TreeNode(39);
tree->root->left->right->left = new TreeNode(40);
// Display Tree Node
tree->preorder();
return 0;
}``````

#### Output

`` 17 11 1 39 40 21 10 2``
``````package main
import "fmt"
// Go Program
// Preorder traversal without recursion
// Using stack
// Binary Tree node
type TreeNode struct {
data int
left * TreeNode
right * TreeNode
}
func getTreeNode(data int) * TreeNode {
var me *TreeNode = &TreeNode {}
// Set node data
me.data = data
me.left = nil
me.right = nil
return me
}
type StackNode struct {
element * TreeNode
next * StackNode
}
func getStackNode(element * TreeNode) * StackNode {
var me *StackNode = &StackNode {}
me.element = element
me.next = nil
return me
}
// Stack Class
type MyStack struct {
top * StackNode
size int
}
func getMyStack() * MyStack {
var me *MyStack = &MyStack {}
me.top = nil
me.size = 0
return me
}
// Add new element into stack
func(this *MyStack) push(element * TreeNode) {
// Create new node
var node * StackNode = getStackNode(element)
node.next = this.top
// new node is new top
this.top = node
// Increase the size
this.size += 1
}
// Remove top element of the stack
func(this *MyStack) pop() {
if this.top != nil {
// next node is new top
this.top = this.top.next
// Reduce size
this.size -= 1
}
}
// Returns the status of empty or non empty stacks
func(this MyStack) isEmpty() bool {
if this.size > 0 && this.top != nil {
return false
} else {
return true
}
}
func(this MyStack) peek() * TreeNode {
if this.isEmpty() {
return nil
}
return this.top.element
}
type BinaryTree struct {
root * TreeNode
}
func getBinaryTree() * BinaryTree {
var me *BinaryTree = &BinaryTree {}
// Set initial tree root to null
me.root = nil
return me
}
// Display preorder view of binary tree
func(this BinaryTree) preorder() {
if this.root != nil {
// Make new stack
var s * MyStack = getMyStack()
var node * TreeNode = this.root
// Display tree element
for (!s.isEmpty() || node != nil) {
if node != nil {
// Display node value
fmt.Print(" ", node.data)
s.push(node)
// Visit to left subtree
node = node.left
} else {
// When node is null
// Get stack top element
node = s.peek()
// Remove top element of the stack
s.pop()
// Visit to left subtree of current node
node = node.right
}
}
} else {
}
}
func main() {
// Create new tree
var tree * BinaryTree = getBinaryTree()
/*
Binary Tree
-------------
17
/    \
11      21
/ \     /  \
1   39  10   2
/
40
*/
tree.root = getTreeNode(17)
tree.root.left = getTreeNode(11)
tree.root.right = getTreeNode(21)
tree.root.right.right = getTreeNode(2)
tree.root.right.left = getTreeNode(10)
tree.root.left.left = getTreeNode(1)
tree.root.left.right = getTreeNode(39)
tree.root.left.right.left = getTreeNode(40)
// Display Tree Node
tree.preorder()
}``````

#### Output

`` 17 11 1 39 40 21 10 2``
``````// Include namespace system
using System;
// Csharp Program
// Preorder traversal without recursion
// Using stack

// Binary Tree node
public class TreeNode
{
public int data;
public TreeNode left;
public TreeNode right;
// Make a tree node
public TreeNode(int data)
{
// Set node data
this.data = data;
this.left = null;
this.right = null;
}
}
public class StackNode
{
public TreeNode element;
public StackNode next;
public StackNode(TreeNode element)
{
this.element = element;
this.next = null;
}
}
// Stack Class
public class MyStack
{
public StackNode top;
public int size;
public MyStack()
{
this.top = null;
this.size = 0;
}
// Add new element into stack
public void push(TreeNode element)
{
// Create new node
StackNode node = new StackNode(element);
node.next = this.top;
// new node is new top
this.top = node;
// Increase the size
this.size += 1;
}
// Remove top element of the stack
public void pop()
{
if (this.top != null)
{
// next node is new top
this.top = this.top.next;
// Reduce size
this.size -= 1;
}
}
// Returns the status of empty or non empty stacks
public Boolean isEmpty()
{
if (this.size > 0 && this.top != null)
{
return false;
}
else
{
return true;
}
}
public TreeNode peek()
{
if (this.isEmpty())
{
return null;
}
return this.top.element;
}
}
public class BinaryTree
{
public TreeNode root;
public BinaryTree()
{
// Set initial tree root to null
this.root = null;
}
// Display preorder view of binary tree
public void preorder()
{
if (this.root != null)
{
// Make new stack
MyStack s = new MyStack();
TreeNode node = this.root;
// Display tree element
while (!s.isEmpty() || node != null)
{
if (node != null)
{
// Display node value
Console.Write(" " + node.data);
s.push(node);
// Visit to left subtree
node = node.left;
}
else
{
// When node is null
// Get stack top element
node = s.peek();
// Remove top element of the stack
s.pop();
// Visit to left subtree of current node
node = node.right;
}
}
}
else
{
}
}
public static void Main(String[] args)
{
// Create new tree
BinaryTree tree = new BinaryTree();
/*
Binary Tree
-------------
17
/    \
11      21
/ \     /  \
1   39  10   2
/
40
*/
tree.root = new TreeNode(17);
tree.root.left = new TreeNode(11);
tree.root.right = new TreeNode(21);
tree.root.right.right = new TreeNode(2);
tree.root.right.left = new TreeNode(10);
tree.root.left.left = new TreeNode(1);
tree.root.left.right = new TreeNode(39);
tree.root.left.right.left = new TreeNode(40);
// Display Tree Node
tree.preorder();
}
}``````

#### Output

`` 17 11 1 39 40 21 10 2``
``````<?php
// Php Program
// Preorder traversal without recursion
// Using stack

// Binary Tree node
class TreeNode
{
public \$data;
public \$left;
public \$right;
// Make a tree node
public  function __construct(\$data)
{
// Set node data
\$this->data = \$data;
\$this->left = NULL;
\$this->right = NULL;
}
}
class StackNode
{
public \$element;
public \$next;
public  function __construct(\$element)
{
\$this->element = \$element;
\$this->next = NULL;
}
}
// Stack Class
class MyStack
{
public \$top;
public \$size;
public  function __construct()
{
\$this->top = NULL;
\$this->size = 0;
}
// Add new element into stack
public  function push(\$element)
{
// Create new node
\$node = new StackNode(\$element);
\$node->next = \$this->top;
// new node is new top
\$this->top = \$node;
// Increase the size
\$this->size += 1;
}
// Remove top element of the stack
public  function pop()
{
if (\$this->top != NULL)
{
// next node is new top
\$this->top = \$this->top->next;
// Reduce size
\$this->size -= 1;
}
}
// Returns the status of empty or non empty stacks
public  function isEmpty()
{
if (\$this->size > 0 && \$this->top != NULL)
{
return false;
}
else
{
return true;
}
}
public  function peek()
{
if (\$this->isEmpty())
{
return NULL;
}
return \$this->top->element;
}
}
class BinaryTree
{
public \$root;
public  function __construct()
{
\$this->root = NULL;
}
// Display preorder view of binary tree
public  function preorder()
{
if (\$this->root != NULL)
{
// Make new stack
\$s = new MyStack();
\$node = \$this->root;
// Display tree element
while (!\$s->isEmpty() || \$node != NULL)
{
if (\$node != NULL)
{
// Display node value
echo(" ".\$node->data);
\$s->push(\$node);
// Visit to left subtree
\$node = \$node->left;
}
else
{
// When node is null
// Get stack top element
\$node = \$s->peek();
// Remove top element of the stack
\$s->pop();
// Visit to left subtree of current node
\$node = \$node->right;
}
}
}
else
{
}
}
}

function main()
{
// Create new tree
\$tree = new BinaryTree();
/*
Binary Tree
-------------
17
/    \
11      21
/ \     /  \
1   39  10   2
/
40
*/
\$tree->root = new TreeNode(17);
\$tree->root->left = new TreeNode(11);
\$tree->root->right = new TreeNode(21);
\$tree->root->right->right = new TreeNode(2);
\$tree->root->right->left = new TreeNode(10);
\$tree->root->left->left = new TreeNode(1);
\$tree->root->left->right = new TreeNode(39);
\$tree->root->left->right->left = new TreeNode(40);
// Display Tree Node
\$tree->preorder();
}
main();``````

#### Output

`` 17 11 1 39 40 21 10 2``
``````// Node JS Program
// Preorder traversal without recursion
// Using stack

// Binary Tree node
class TreeNode
{
// Make a tree node
constructor(data)
{
// Set node data
this.data = data;
this.left = null;
this.right = null;
}
}
class StackNode
{
constructor(element)
{
this.element = element;
this.next = null;
}
}
// Stack Class
class MyStack
{
constructor()
{
this.top = null;
this.size = 0;
}
// Add new element into stack
push(element)
{
// Create new node
var node = new StackNode(element);
node.next = this.top;
// new node is new top
this.top = node;
// Increase the size
this.size += 1;
}
// Remove top element of the stack
pop()
{
if (this.top != null)
{
// next node is new top
this.top = this.top.next;
// Reduce size
this.size -= 1;
}
}
// Returns the status of empty or non empty stacks
isEmpty()
{
if (this.size > 0 && this.top != null)
{
return false;
}
else
{
return true;
}
}
peek()
{
if (this.isEmpty())
{
return null;
}
return this.top.element;
}
}
class BinaryTree
{
constructor()
{
this.root = null;
}
// Display preorder view of binary tree
preorder()
{
if (this.root != null)
{
// Make new stack
var s = new MyStack();
var node = this.root;
// Display tree element
while (!s.isEmpty() || node != null)
{
if (node != null)
{
// Display node value
process.stdout.write(" " + node.data);
s.push(node);
// Visit to left subtree
node = node.left;
}
else
{
// When node is null
// Get stack top element
node = s.peek();
// Remove top element of the stack
s.pop();
// Visit to left subtree of current node
node = node.right;
}
}
}
else
{
}
}
}

function main()
{
// Create new tree
var tree = new BinaryTree();
/*
Binary Tree
-------------
17
/    \
11      21
/ \     /  \
1   39  10   2
/
40
*/
tree.root = new TreeNode(17);
tree.root.left = new TreeNode(11);
tree.root.right = new TreeNode(21);
tree.root.right.right = new TreeNode(2);
tree.root.right.left = new TreeNode(10);
tree.root.left.left = new TreeNode(1);
tree.root.left.right = new TreeNode(39);
tree.root.left.right.left = new TreeNode(40);
// Display Tree Node
tree.preorder();
}
main();``````

#### Output

`` 17 11 1 39 40 21 10 2``
``````#  Python 3 Program
#  Preorder traversal without recursion
#  Using stack

#  Binary Tree node
class TreeNode :
#  Make a tree node
def __init__(self, data) :
#  Set node data
self.data = data
self.left = None
self.right = None

class StackNode :
def __init__(self, element) :
self.element = element
self.next = None

#  Stack Class
class MyStack :
def __init__(self) :
self.top = None
self.size = 0

#  Add new element into stack
def push(self, element) :
#  Create new node
node = StackNode(element)
node.next = self.top
#  new node is new top
self.top = node
#  Increase the size
self.size += 1

#  Remove top element of the stack
def pop(self) :
if (self.top != None) :
#  next node is new top
self.top = self.top.next
#  Reduce size
self.size -= 1

#  Returns the status of empty or non empty stacks
def isEmpty(self) :
if (self.size > 0 and self.top != None) :
return False
else :
return True

def peek(self) :
if (self.isEmpty()) :
return None

return self.top.element

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

#  Display preorder view of binary tree
def preorder(self) :
if (self.root != None) :
#  Make new stack
s = MyStack()
node = self.root
#  Display tree element
while (not s.isEmpty() or node != None) :
if (node != None) :
#  Display node value
print(" ", node.data, end = "")
s.push(node)
#  Visit to left subtree
node = node.left
else :
#  When node is null
#  Get stack top element
node = s.peek()
#  Remove top element of the stack
s.pop()
#  Visit to left subtree of current node
node = node.right

else :

def main() :
#  Create new tree
tree = BinaryTree()
#    Binary Tree
#    -------------
#          17
#        /    \
#      11      21
#     / \     /  \
#    1   39  10   2
#       /
#      40
tree.root = TreeNode(17)
tree.root.left = TreeNode(11)
tree.root.right = TreeNode(21)
tree.root.right.right = TreeNode(2)
tree.root.right.left = TreeNode(10)
tree.root.left.left = TreeNode(1)
tree.root.left.right = TreeNode(39)
tree.root.left.right.left = TreeNode(40)
#  Display Tree Node
tree.preorder()

if __name__ == "__main__": main()``````

#### Output

``  17  11  1  39  40  21  10  2``
``````#  Ruby Program
#  Preorder traversal without recursion
#  Using stack

#  Binary Tree node
class TreeNode
# Define the accessor and reader of class TreeNode
attr_accessor :data, :left, :right
#  Make a tree node
def initialize(data)
#  Set node data
self.data = data
self.left = nil
self.right = nil
end

end

class StackNode
# Define the accessor and reader of class StackNode
attr_accessor :element, :next
def initialize(element)
self.element = element
self.next = nil
end

end

#  Stack Class
class MyStack
# Define the accessor and reader of class MyStack
attr_accessor :top, :size
def initialize()
self.top = nil
self.size = 0
end

#  Add new element into stack
def push(element)
#  Create new node
node = StackNode.new(element)
node.next = self.top
#  new node is new top
self.top = node
#  Increase the size
self.size += 1
end

#  Remove top element of the stack
def pop()
if (self.top != nil)
#  next node is new top
self.top = self.top.next
#  Reduce size
self.size -= 1
end

end

#  Returns the status of empty or non empty stacks
def isEmpty()
if (self.size > 0 && self.top != nil)
return false
else

return true
end

end

def peek()
if (self.isEmpty())
return nil
end

return self.top.element
end

end

class BinaryTree
# Define the accessor and reader of class BinaryTree
attr_accessor :root
def initialize()
self.root = nil
end

#  Display preorder view of binary tree
def preorder()
if (self.root != nil)
#  Make new stack
s = MyStack.new()
node = self.root
#  Display tree element
while (!s.isEmpty() || node != nil)
if (node != nil)
#  Display node value
print(" ", node.data)
s.push(node)
#  Visit to left subtree
node = node.left
else

#  When node is null
#  Get stack top element
node = s.peek()
#  Remove top element of the stack
s.pop()
#  Visit to left subtree of current node
node = node.right
end

end

else

end

end

end

def main()
#  Create new tree
tree = BinaryTree.new()
#    Binary Tree
#    -------------
#          17
#        /    \
#      11      21
#     / \     /  \
#    1   39  10   2
#       /
#      40
tree.root = TreeNode.new(17)
tree.root.left = TreeNode.new(11)
tree.root.right = TreeNode.new(21)
tree.root.right.right = TreeNode.new(2)
tree.root.right.left = TreeNode.new(10)
tree.root.left.left = TreeNode.new(1)
tree.root.left.right = TreeNode.new(39)
tree.root.left.right.left = TreeNode.new(40)
#  Display Tree Node
tree.preorder()
end

main()``````

#### Output

`` 17 11 1 39 40 21 10 2``
``````// Scala Program
// Preorder traversal without recursion
// Using stack

// Binary Tree node
class TreeNode(var data: Int,
var left: TreeNode,
var right: TreeNode)
{
// Make a tree node
def this(data: Int)
{
// Set node data
this(data, null, null);
}
}
class StackNode(var element: TreeNode,
var next: StackNode)
{
def this(element: TreeNode)
{
this(element, null);
}
}
// Stack Class
class MyStack(var top: StackNode,
var size: Int)
{
def this()
{
this(null, 0);
}
// Add new element into stack
def push(element: TreeNode): Unit = {
// Create new node
var node: StackNode = new StackNode(element);
node.next = this.top;
// new node is new top
this.top = node;
// Increase the size
this.size += 1;
}
// Remove top element of the stack
def pop(): Unit = {
if (this.top != null)
{
// next node is new top
this.top = this.top.next;
// Reduce size
this.size -= 1;
}
}
// Returns the status of empty or non empty stacks
def isEmpty(): Boolean = {
if (this.size > 0 && this.top != null)
{
return false;
}
else
{
return true;
}
}
def peek(): TreeNode = {
if (isEmpty())
{
return null;
}
return this.top.element;
}
}
class BinaryTree(var root: TreeNode)
{
def this()
{
this(null);
}
// Display preorder view of binary tree
def preorder(): Unit = {
if (this.root != null)
{
// Make new stack
var s: MyStack = new MyStack();
var node: TreeNode = this.root;
// Display tree element
while (!s.isEmpty() || node != null)
{
if (node != null)
{
// Display node value
print(" " + node.data);
s.push(node);
// Visit to left subtree
node = node.left;
}
else
{
// When node is null
// Get stack top element
node = s.peek();
// Remove top element of the stack
s.pop();
// Visit to left subtree of current node
node = node.right;
}
}
}
else
{
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
// Create new tree
var tree: BinaryTree = new BinaryTree();
/*
Binary Tree
-------------
17
/    \
11      21
/ \     /  \
1   39  10   2
/
40
*/
tree.root = new TreeNode(17);
tree.root.left = new TreeNode(11);
tree.root.right = new TreeNode(21);
tree.root.right.right = new TreeNode(2);
tree.root.right.left = new TreeNode(10);
tree.root.left.left = new TreeNode(1);
tree.root.left.right = new TreeNode(39);
tree.root.left.right.left = new TreeNode(40);
// Display Tree Node
tree.preorder();
}
}``````

#### Output

`` 17 11 1 39 40 21 10 2``
``````// Swift 4 Program
// Preorder traversal without recursion
// Using stack

// Binary Tree node
class TreeNode
{
var data: Int;
var left: TreeNode? ;
var right: TreeNode? ;
// Make a tree node
init(_ data: Int)
{
// Set node data
self.data = data;
self.left = nil;
self.right = nil;
}
}
class StackNode
{
var element: TreeNode? ;
var next: StackNode? ;
init(_ element: TreeNode? )
{
self.element = element;
self.next = nil;
}
}
// Stack Class
class MyStack
{
var top: StackNode? ;
var size: Int;
init()
{
self.top = nil;
self.size = 0;
}
// Add new element into stack
func push(_ element: TreeNode? )
{
// Create new node
let node: StackNode = StackNode(element);
node.next = self.top;
// new node is new top
self.top = node;
// Increase the size
self.size += 1;
}
// Remove top element of the stack
func pop()
{
if (self.top  != nil)
{
// next node is new top
self.top = self.top!.next;
// Reduce size
self.size -= 1;
}
}
// Returns the status of empty or non empty stacks
func isEmpty() -> Bool
{
if (self.size > 0 && self.top  != nil)
{
return false;
}
else
{
return true;
}
}
func peek() -> TreeNode?
{
if (self.isEmpty())
{
return nil;
}
return self.top!.element;
}
}
class BinaryTree
{
var root: TreeNode? ;
init()
{
self.root = nil;
}
// Display preorder view of binary tree
func preorder()
{
if (self.root  != nil)
{
// Make new stack
let s: MyStack = MyStack();
var node: TreeNode? = self.root;
// Display tree element
while (!s.isEmpty() || node  != nil)
{
if (node  != nil)
{
// Display node value
print(" ", node!.data, terminator: "");
s.push(node);
// Visit to left subtree
node = node!.left;
}
else
{
// When node is null
// Get stack top element
node = s.peek();
// Remove top element of the stack
s.pop();
// Visit to left subtree of current node
node = node!.right;
}
}
}
else
{
}
}
}
func main()
{
// Create new tree
let tree: BinaryTree = BinaryTree();
/*
Binary Tree
-------------
17
/    \
11      21
/ \     /  \
1   39  10   2
/
40
*/
tree.root = TreeNode(17);
tree.root!.left = TreeNode(11);
tree.root!.right = TreeNode(21);
tree.root!.right!.right = TreeNode(2);
tree.root!.right!.left = TreeNode(10);
tree.root!.left!.left = TreeNode(1);
tree.root!.left!.right = TreeNode(39);
tree.root!.left!.right!.left = TreeNode(40);
// Display Tree Node
tree.preorder();
}
main();``````

#### Output

``  17  11  1  39  40  21  10  2``
``````// Kotlin Program
// Preorder traversal without recursion
// Using stack

// Binary Tree node
class TreeNode
{
var data: Int;
var left: TreeNode ? ;
var right: TreeNode ? ;
// Make a tree node
constructor(data: Int)
{
// Set node data
this.data = data;
this.left = null;
this.right = null;
}
}
class StackNode
{
var element: TreeNode ? ;
var next: StackNode ? ;
constructor(element: TreeNode ? )
{
this.element = element;
this.next = null;
}
}
// Stack Class
class MyStack
{
var top: StackNode ? ;
var size: Int;
constructor()
{
this.top = null;
this.size = 0;
}
// Add new element into stack
fun push(element: TreeNode ? ): Unit
{
// Create new node
val node: StackNode = StackNode(element);
node.next = this.top;
// new node is new top
this.top = node;
// Increase the size
this.size += 1;
}
// Remove top element of the stack
fun pop(): Unit
{
if (this.top != null)
{
// next node is new top
this.top = this.top?.next;
// Reduce size
this.size -= 1;
}
}
// Returns the status of empty or non empty stacks
fun isEmpty(): Boolean
{
if (this.size > 0 && this.top != null)
{
return false;
}
else
{
return true;
}
}
fun peek(): TreeNode ?
{
if (this.isEmpty())
{
return null;
}
return this.top?.element;
}
}
class BinaryTree
{
var root: TreeNode ? ;
constructor()
{
this.root = null;
}
// Display preorder view of binary tree
fun preorder(): Unit
{
if (this.root != null)
{
// Make new stack
val s: MyStack = MyStack();
var node: TreeNode ? = this.root;
// Display tree element
while (!s.isEmpty() || node != null)
{
if (node != null)
{
// Display node value
print(" " + node.data);
s.push(node);
// Visit to left subtree
node = node.left;
}
else
{
// When node is null
// Get stack top element
node = s.peek();
// Remove top element of the stack
s.pop();
// Visit to left subtree of current node
node = node?.right;
}
}
}
else
{
}
}
}
fun main(args: Array < String > ): Unit
{
// Create new tree
val tree: BinaryTree = BinaryTree();
/*
Binary Tree
-------------
17
/    \
11      21
/ \     /  \
1   39  10   2
/
40
*/
tree.root = TreeNode(17);
tree.root?.left = TreeNode(11);
tree.root?.right = TreeNode(21);
tree.root?.right?.right = TreeNode(2);
tree.root?.right?.left = TreeNode(10);
tree.root?.left?.left = TreeNode(1);
tree.root?.left?.right = TreeNode(39);
tree.root?.left?.right?.left = TreeNode(40);
// Display Tree Node
tree.preorder();
}``````

#### Output

`` 17 11 1 39 40 21 10 2``

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.