Preorder, Inorder and Postorder traversals
Tree traversal using preorder, inorder & postorder tree traversals
-
In Pre-Order tree traversal, the root data is accessed as soon as the root is visited. After the root data is accessed, the left sub-tree of the root node is visited and then the right sub-tree. The traversal is recursive in nature, i.e the left sub-tree and the right sub-tree are traversed similarly to the root. Example of pre-order traversal of a binary tree : 9, 5, 3, 7, 16, 12, 18
-
In In-Order tree traversal, the data in left sub-tree is accessed first, followed by the data of the root, followed by the data in the right sub-tree. The traversal is recursive in nature. Example of an in-order traversal of a binary tree : 3, 5, 7, 9, 12, 16, 18
-
In Post-Order tree traversal, the data in left sub-tree is accessed first, followed by the data in the right sub-tree, followed by the data in the root. The traversal is recursive in nature. Example of a post-order traversal of a binary tree : 3, 7, 5, 12, 18, 16, 9
Note: Accessing / Processing the data of a node is different from visiting the node.
Data structure used for pre-order, in-order and post-order traversals : Stack
Time complexity of pre-order, in-order and post-order traversals : O(n), where n is the number of nodes in the graph.
Python
Pre-order, In-order and Post-order traversals in Python
from collections import deque
class Node :
def __init__(self, val, left_node, right_node) :
self.val = val
self.left = left_node
self.right = right_node
def PreOrderRec(node) :
if node :
print(node.val, end = ' ')
PreOrderRec(node.left)
PreOrderRec(node.right)
def PreOrder(node) :
stack = deque()
while (node or stack) :
# If node is None
if node == None:
node = stack.popleft() # Node at the top of stack
node = node.right
if node :
print(node.val, end = ' ')
stack.appendleft(node)
node = node.left
def InOrderRec(node) :
if node :
InOrderRec(node.left)
print(node.val, end = ' ')
InOrderRec(node.right)
def InOrder(node) :
stack = deque()
while (node or stack) :
# If node is None
if node == None :
node = stack.popleft() # Node at the top of stack
print(node.val, end =' ')
if node :
stack.appendleft(node)
node = node.left
def PostOrderRec(node) :
if node :
PostOrderRec(node.left)
PostOrderRec(node.right)
print(node.val, end = ' ')
def PostOrder(node) :
stack_postorder = deque()
stack = deque()
if node :
stack.append(node)
while (stack) :
# stack_postorder stores the order of the elements to be traversed in
# postorder
stack_postorder.appendleft(stack.popleft())
if stack_postorder[0].left :
stack.appendleft(stack_postorder[0].left)
if stack_postorder[0].right :
stack.appendleft(stack_postorder[0].right)
while (stack_postorder) :
print(stack_postorder.popleft().val, ' ')
def main() :
node_3 = Node(3, None, None); # Leaf Node
node_7 = Node(7, None, None); # Leaf Node
node_12 = Node(12, None, None); # Leaf Node
node_18 = Node(18, None, None); # Leaf Node
node_16 = Node(16, node_12, node_18)
node_5 = Node(5, node_3, node_7)
root = Node(9, node_5, node_16)
print("---- Recursive approach ----")
print("Pre-Order Traversal :", end = ' ')
PreOrderRec(root)
print("\nIn-Order Traversal :", end = ' ')
InOrderRec(root)
print("\nPost-Order Traversal :", end = ' ')
PostOrderRec(root)
print("\n\n---- Iterative approach ----")
print("Pre-Order Traversal :", end = ' ')
PreOrderRec(root)
print("\nIn-Order Traversal :", end = ' ')
InOrderRec(root)
print("\nPost-Order Traversal :", end = ' ')
PostOrderRec(root)
if __name__ == "__main__" :
main()
Output
---- Recursive approach ----
Pre-Order Traversal : 9 5 3 7 16 12 18
In-Order Traversal : 3 5 7 9 12 16 18
Post-Order Traversal : 3 7 5 12 18 16 9
---- Iterative approach ----
Pre-Order Traversal : 9 5 3 7 16 12 18
In-Order Traversal : 3 5 7 9 12 16 18
Post-Order Traversal : 3 7 5 12 18 16 9
Java
Java program for Pre-order, In-order and Post-order tree traversals.
import java.util.Stack;
class TreeTraversals {
static class Node {
int data;
Node left, right;
Node (int arg_data) {
data = arg_data;
left = null;
right = null;
}
}
void PreOrderRecursive (Node node) {
if (node != null) {
System.out.print(node.data + " "); // Access the data
PreOrderRecursive(node.left); // Visit current node's left node
PreOrderRecursive(node.right); // Visit current node's right node
}
}
void PreOrder (Node node) {
Stack<Node> stk = new Stack<>();
while (node != null || !stk.empty()) {
if (node == null) {
node = stk.peek();
stk.pop();
node = node.right;
}
if (node != null) {
System.out.print (node.data + " ");
stk.push(node);
node = node.left;
}
}
}
void InOrderRecursive (Node node) {
if (node != null) {
InOrderRecursive (node.left); // Visit current node's left node
System.out.print (node.data + " "); // Access the data
InOrderRecursive (node.right); // Visit current node's right node
}
}
void InOrder (Node node) {
Stack<Node> stk = new Stack<>();
while (node != null || !stk.empty()) {
if (node == null) {
node = stk.peek();
stk.pop();
System.out.print (node.data + " ");
node = node.right;
}
if (node != null) {
stk.push(node);
node = node.left;
}
}
}
void PostOrderRecursive (Node node) {
if (node != null) {
PostOrderRecursive (node.left); // Visit current node's left node
PostOrderRecursive (node.right); // Visit current node's right node
System.out.print (node.data + " "); // Access the data
}
}
void PostOrder (Node node) {
Stack<Node> stk_postorder = new Stack<>();
Stack<Node> stk = new Stack<>();
if (node != null) {
stk.push(node);
}
while (!stk.empty()) {
stk_postorder.push(stk.peek());
stk.pop();
if (stk_postorder.peek().left != null) {
stk.push(stk_postorder.peek().left);
}
if (stk_postorder.peek().right != null) {
stk.push(stk_postorder.peek().right);
}
}
while (!stk_postorder.empty()) {
System.out.print(stk_postorder.peek().data + " ");
stk_postorder.pop();
}
}
/* Constructed binary tree is
9
/ \
5 16
/ \ / \
3 7 12 18
*/
public static void main (String[] args) {
Node root = new Node(9);
root.left = new Node(5);
root.right = new Node(16);
root.left.left = new Node(3);
root.left.right = new Node(7);
root.right.left = new Node(12);
root.right.right = new Node(18);
TreeTraversals t = new TreeTraversals();
System.out.println ("---- Recursive approach ----\n");
System.out.print("Pre-Order traversal : "); t.PreOrderRecursive (root); System.out.print("\n");
System.out.print("In-Order traversal : "); t.InOrderRecursive (root); System.out.print("\n");
System.out.print("Post-Order traversal : "); t.PostOrderRecursive (root); System.out.print("\n");
System.out.println ("\n---- Stack based approach ----\n");
System.out.print("Pre-Order traversal : "); t.PreOrder (root); System.out.print("\n");
System.out.print("In-Order traversal : "); t.InOrder (root); System.out.print("\n");
System.out.print("Post-Order traversal : "); t.PostOrder (root); System.out.print("\n");
// Cleanup
root.right.right = null;
root.right.left = null;
root.left.right = null;
root.left.left = null;
root.right = null;
root.left = null;
root = null;
}
}
Output
---- Recursive approach ----
Pre-Order traversal : 9 5 3 7 16 12 18
In-Order traversal : 3 5 7 9 12 16 18
Post-Order traversal : 3 7 5 12 18 16 9
---- Stack based approach ----
Pre-Order traversal : 9 5 3 7 16 12 18
In-Order traversal : 3 5 7 9 12 16 18
Post-Order traversal : 3 7 5 12 18 16 9
C++ program for PreOrder, InOrder and PostOrder tree traversals.
#include <iostream>
#include <stack>
using namespace std;
class Node{
public:
Node(int n):data(n),left(NULL),right(NULL){
}
Node * left;
Node * right;
int data;
};
void PreOrderRecursive(Node * node){
if (node != NULL) {
cout << node->data << " "; // Access the data
PreOrderRecursive(node->left); // Visit current node's left node
PreOrderRecursive(node->right); // Visit current node's right node
}
}
void PreOrder (Node * node) {
stack<Node*> stk;
while (node != NULL || !stk.empty()) {
if (node == NULL) {
node = stk.top();
stk.pop();
node = node->right;
}
if (node != NULL) {
cout << node->data << " ";
stk.push(node);
node = node->left;
}
}
}
void InOrderRecursive (Node * node) {
if (node != NULL) {
InOrderRecursive(node->left);
cout << node->data << " ";
InOrderRecursive(node->right);
}
}
void InOrder (Node * node) {
stack<Node *> stk;
while (node != NULL || !stk.empty()) {
if (node == NULL) {
node = stk.top();
stk.pop();
cout << node->data << " ";
node = node->right;
}
if (node != NULL) {
stk.push(node);
node = node->left;
}
}
}
void PostOrderRecursive (Node * node) {
if (node != NULL) {
PostOrderRecursive(node->left);
PostOrderRecursive(node->right);
cout << node->data << " ";
}
}
void PostOrder (Node * node) {
stack<Node *> stk_postorder;
stack<Node *> stk;
if (node != NULL) {
stk.push(node);
}
while (!stk.empty()) {
node = stk.top();
stk_postorder.push(node);
stk.pop();
if (node->left != NULL) {
stk.push(node->left);
}
if (node->right != NULL) {
stk.push(node->right);
}
}
while (!stk_postorder.empty()) {
cout << stk_postorder.top()->data << " ";
stk_postorder.pop();
}
}
/* Constructed binary tree is
9
/ \
5 16
/ \ / \
3 7 12 18
*/
int main() {
Node *root = new Node(9);
root->left = new Node(5);
root->right = new Node(16);
root->left->left = new Node(3);
root->left->right = new Node(7);
root->right->left = new Node(12);
root->right->right = new Node(18);
cout << "---- Recursive approach ----" << endl;
cout << "Pre-Order traversal: "; PreOrderRecursive(root); cout << endl;
cout << "In-Order traversal: "; InOrderRecursive(root); cout << endl;
cout << "Post-Order traversal: "; PostOrderRecursive(root); cout << endl;
cout << "---- Stack based approach ----" << endl;
cout << "Pre-Order traversal: "; PreOrder(root); cout << endl;
cout << "In-Order traversal: "; InOrder(root); cout << endl;
cout << "Post-Order traversal: "; PostOrder(root); cout << endl;
// Cleanup
delete root->right->right;
delete root->right->left;
delete root->left->right;
delete root->left->left;
delete root->right;
delete root->left;
delete root;
return 0;
}
Output
---- Recursive approach ----
Pre-Order traversal: 9 5 3 7 16 12 18
In-Order traversal: 3 5 7 9 12 16 18
Post-Order traversal: 3 7 5 12 18 16 9
---- Stack based approach ----
Pre-Order traversal: 9 5 3 7 16 12 18
In-Order traversal: 3 5 7 9 12 16 18
Post-Order traversal: 3 7 5 12 18 16 9