Preorder, Inorder and Postorder tree traversals
PreOrder traversal
- 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 child of the root node is visited and then the right child.
- The traversal is recursive in nature, i.e the left child and the right child are traversed similarly to the parent node.
- Thus the preorder traversal recursively follows the sequence Print node’s data -> Visit Left_Child_Of_Node -> Visit Right_Child_Of_Node.
Algorithm PreOrder Traversal
| Recursive | Iterative |
|---|---|
| PreOrder ( Node node ) If ( node != null ) then Print node’s data PreOrder ( node’s left child ) PreOrder ( node’s right child ) |
PreOrder ( Node node ) Stack stk While ( node != NULL or stk is not empty ) do If ( node != NULL ) then Print node’s data Push node on stack stk. node = node’s left child. If ( node == NULL ) then node = node at stk top. Pop stk. node = node’s right child. |
Example of pre-order traversal : 9, 5, 3, 7
InOrder Traversal
- In In-Order tree traversal, the left child of a node is visited first, followed by the data of the node and then the right child of the node.
- The traversal is recursive in nature. i.e the left child and the right child are traversed similarly to the parent node.
- Thus the preorder traversal recursively follows the sequence Visit Left_Child_Of_Node -> Print node’s data -> Visit Right_Child_Of_Node.
Algorithm InOrder Traversal
| Recursive | Iterative |
|---|---|
| InOrder ( Node * node ) If ( node != null ) then InOrder ( node’s left child ) Print node’s data InOrder ( node’s right child ) |
InOrder ( Node node ) Stack stk While ( node != NULL or stk is not empty ) do If ( node != NULL ) then Push node on stk top. node = node’s left child. If ( node == NULL ) then node = node at stk top. Pop stk. Print node’s data node = node’s right child. |
Example of an in-order traversal : 3, 5, 7, 9
PostOrder Traversal
- In Post-Order tree traversal, the left child of a node is visited first, then the right child of the node followed by the data of the node.
- Post order traversal is recursive in nature. i.e the left child and the right child are traversed similarly to the parent node.
- Thus the preorder traversal recursively follows the sequence Visit Left_Child_Of_Node -> Visit Right_Child_Of_Node -> Print node’s data.
Algorithm PostOrder Traversal
The iterative algorithm for PostOrder traversal makes use of 2 stacks.
- Stack stk is used for processing the nodes.
- Stack stk_postorder is used for storing the postorder of the nodes.
| Recursive | Iterative |
|---|---|
| PostOrder ( Node * node ) If ( node != null ) then PostOrder ( node’s left child ) PostOrder ( node’s right child ) Print node’s data |
PostOrder ( Node node ) Stack stk Stack stk_postorder If ( node != NULL ) then Push node on stk top. While ( stk is not empty ) do node = node at stk top. Pop stk top. Push node on stk_postorder. If ( node’s left child != null ) then Push node’s left child on stk. If ( node’s right child != null ) then Push node’s right child on stk. While ( stk_postorder is not empty ) do Print data of node at the top of stk_postoder. Pop stk_postoder. |
Example of an post-order traversal : 3, 7, 5, 9
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.
Pre-Order, In-Order and Post-Order traversal implementation
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 :
print(node.val, end = ' ')
stack.appendleft(node)
node = node.left
if node == None:
node = stack.popleft() # Node at the top of stack
node = node.right
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 :
stack.appendleft(node)
node = node.left
if node == None :
node = stack.popleft() # Node at the top of stack
print(node.val, end =' ')
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 method ----")
print("Pre-Order :", end = ' ')
PreOrderRec(root)
print("\nIn-Order :", end = ' ')
InOrderRec(root)
print("\nPost-Order :", end = ' ')
PostOrderRec(root)
print("\n\n---- Stack based method ----")
print("Pre-Order :", end = ' ')
PreOrderRec(root)
print("\nIn-Order :", end = ' ')
InOrderRec(root)
print("\nPost-Order :", end = ' ')
PostOrderRec(root)
if __name__ == "__main__" :
main()
Output
---- Recursive method ----
Pre-Order : 9 5 3 7 16 12 18
In-Order : 3 5 7 9 12 16 18
Post-Order : 3 7 5 12 18 16 9
---- Stack based method ----
Pre-Order : 9 5 3 7 16 12 18
In-Order : 3 5 7 9 12 16 18
Post-Order : 3 7 5 12 18 16 9
#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) {
cout << node->data << " ";
stk.push(node);
node = node->left;
}
if (node == NULL) {
node = stk.top();
stk.pop();
node = node->right;
}
}
}
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) {
stk.push(node);
node = node->left;
}
if (node == NULL) {
node = stk.top();
stk.pop();
cout << node->data << " ";
node = node->right;
}
}
}
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 method ----" << endl;
cout << "Pre-Order : "; PreOrderRecursive(root); cout << endl;
cout << "In-Order : "; InOrderRecursive(root); cout << endl;
cout << "Post-Order : "; PostOrderRecursive(root); cout << endl;
cout << "---- Stack based ----" << endl;
cout << "Pre-Order : "; PreOrder(root); cout << endl;
cout << "In-Order : "; InOrder(root); cout << endl;
cout << "Post-Order : "; 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 method ----
Pre-Order : 9 5 3 7 16 12 18
In-Order : 3 5 7 9 12 16 18
Post-Order : 3 7 5 12 18 16 9
---- Stack based ----
Pre-Order : 9 5 3 7 16 12 18
In-Order : 3 5 7 9 12 16 18
Post-Order : 3 7 5 12 18 16 9
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) {
System.out.print (node.data + " ");
stk.push(node);
node = node.left;
}
if (node == null) {
node = stk.peek();
stk.pop();
node = node.right;
}
}
}
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) {
stk.push(node);
node = node.left;
}
if (node == null) {
node = stk.peek();
stk.pop();
System.out.print (node.data + " ");
node = node.right;
}
}
}
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 method ----\n");
System.out.print("Pre-Order : "); t.PreOrderRecursive (root); System.out.print("\n");
System.out.print("In-Order : "); t.InOrderRecursive (root); System.out.print("\n");
System.out.print("Post-Order : "); t.PostOrderRecursive (root); System.out.print("\n");
System.out.println ("\n---- Stack based method ----\n");
System.out.print("Pre-Order : "); t.PreOrder (root); System.out.print("\n");
System.out.print("In-Order : "); t.InOrder (root); System.out.print("\n");
System.out.print("Post-Order : "); 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 method ----
Pre-Order : 9 5 3 7 16 12 18
In-Order : 3 5 7 9 12 16 18
Post-Order : 3 7 5 12 18 16 9
---- Stack based method ----
Pre-Order : 9 5 3 7 16 12 18
In-Order : 3 5 7 9 12 16 18
Post-Order : 3 7 5 12 18 16 9