Runway reservation system using binary search tree

Runway reservation system

Today, we will discuss a very interesting and real life problem. Let’s say there is a runway, a very busy runway. Flights needs to reserve their landing on this runway in advance, that means reservations are done in future time.  Reservation request contains time of landing. A flight is given landing slot or reservation only if there is no flight schedule to land with K mins of requested landing time. This problem is to design strong>runway reservation system or scheduling system.

There are two notions associated with system involving time. First, adding a reservation to set, i.e insertion operation. Addition of a reservation to set should be done only if constraints are not violated.

Second, if requested reservation time is less than current time, i.e. plane has already landed as per request, that reservation should be removed from the set, so that new reservation requests for that time can be accommodated if they satisfy constraints of the system.

Let’s take an example and see if we understood the problem correctly. Consider current time is t =30  and we have already scheduled flights at 35, 44 and 57. At t =30, we get another request for landing at t =53. Can we accommodate it? Yes if K =3 as there is no flights scheduled 3 minutes before or after requested reservation time. Hence, now our set become [35, 44, 53, 57]. If at t= 32, another request comes for landing at 45, can we take that? Nope, as it violate 3 min constraints as there is already a landing scheduled at 44. What if request comes for t =25 at t =30. Well, that is not possible as system allows reservation to be done in future only.

This hopefully completely clarifies requirements of system.

Runway reservation system : Data structures

We will consider data structure one by one and see what is best suited for solution in terms of time complexity. Our goal is to achieve, insertion, removal and constraint check in O(log n) time complexity.

First, let’s take unsorted array or list. Store all reservations granted into unsorted array. What is complexity of insertion. It’s O(1) as new reservation will always be added at the end of array. How about constraint check? There is no ordering of reservation, hence you have to scan entire array for constraint check, to see if there is no flight within 3 minutes time of requested reservation time, leading to O(N) complexity. Removal of reservation from unsorted array is also O(N) complexity.

Second, consider sorted array. We have all requests stored in sorted order. What advantage does it give us? Insertion point of new reservation can be found using binary search algorithm with log (N) complexity. That means we can find R[i] which is greater that request time in O(log n) time.

Constraint check can be done by checking R[i] and R[i-1] against requested reservation time, in constant time, hence complexity of O(1).

What happens when we try to insert a request in sorted array? We have to shift all requests greater than request time by one. In worst case, that becomes O(N).

To solve, insertion limitation, we can use sorted list, where insertion complexity is O(1), however, we lose advantage of binary search and finding insertion place becomes O(N). Sorted list solves one problem but worsen another.

How about heaps? Insertion and removal in a heap takes O(log n) time, however, constraint check to check that there is no reservation for landing with K minutes of requested time will take O(n).

Closest we came to our desired time complexity was with sorted array. If we can solve insertion in O(log n) time, we are good to go. That’s where binary search tree comes into picture.

Binary search tree has an invariant which states that all nodes on left side are less and all nodes on right side are greater than the node itself. We will be using this invariant to solve our problem.

As we discussed in post Insert a node in BST, insertion operation is dependent on height of tree, if height of tree is h, then insertion complexity will be O(h), same goes for deletion of node. While constraint check can be done while searching for insertion place in BST, complexity of constraint check also is O(h).

Now, based on nature of tree (balanced or skewed), h may vary between log n to n and hence the insertion, constraint check and removal complexity. So, we are still quite not there.

To make height of binary search tree of order O(log n), we need to somehow balance binary search tree. However, this entire discussion explains how can we arrive at solution of a given problem.

Considering that there is sufficient randomization in reservation request, implementation using simple binary search tree would be like this.

Runway reservation system : Implementation

 Source
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
 
struct node{
	int value;
	struct node *left;
	struct node *right;
};
typedef struct node Node;
 
void inorderTraversal(Node * root){
	if(!root)
		return;
 
	inorderTraversal(root->left);
	printf("%d ", root->value);
	inorderTraversal(root->right);
}
Node *createNode(int value){
	Node * newNode =  (Node *)malloc(sizeof(Node));
	newNode->value = value;
	newNode->right= NULL;
	newNode->left = NULL;
 
	return newNode;
}
Node *addNode(Node *node, int value, int K){
	if(!node){
		return createNode(value);
	}
	if ( node->value + K > value && node->value - K < value ){
		return node;
	}
	if (node->value > value)
		node->left = addNode(node->left, value, K);
	else
		node->right = addNode(node->right, value, K);
 
	return node;
}
 
/* Driver program for the function written above */
int main(){
	Node *root = NULL;
	//Creating a binary tree
	root = addNode(root, 30, 3);
	root = addNode(root, 20, 3);
	root = addNode(root, 15, 3);
	root = addNode(root, 25, 3);
	root = addNode(root, 40, 3);
	root = addNode(root, 38, 3);
	root = addNode(root, 45, 3);
        inorderTraversal(root);
	return 0;
}

Please share if something is wrong or missing. Would love to hear from you. Sharing is caring.

Search in binary search tree

In last post insert a node in BST, we learned basics about binary search tree and how to insert a node in it. Today, we will discuss how to search a value in binary search tree.

As we already know that binary search tree has this property where all nodes on left side of node are smaller and all nodes on right side of node are greater than it. So, when searching for a value in BST, we can safely discard half of tree (given tree balanced) with each comparison. Remember something? Binary search algorithm!!

Algorithm to search in binary search tree

1. Start with root node, make it currentNode
2. While currentNode is not NULL
   2.1 Compare currentNode->value with searchedKey
        2.1.1 If currentNode->value == searchedKey, return currentNode
        2.1.2 If currentNode->value > searchedKey, 
              make currentNode = currentNode->left;
        2.1.3 If currentNode->value < searchedKey
              make currentNode = currentNode->right;
3. return currentNode;

Implementation is pretty simple and classic case for divide and conquer algorithm.

Recursive implementation of same is :

Complexity of search in binary search tree in worst case is O(N). Again misconception that it is O(log N). It is O(log N) only when it is given that BST is balanced. If tree is completely skewed, complexity is O(N)

Please share if you find something wrong or missing. Sharing is caring.

Insert node in binary search tree

Insert node in binary search tree

To start binary search tree sessions, let us understand what is binary search and how can we insert node in binary search tree?

First of all, what is a binary search tree? A binary search tree is collection of nodes where each node has maximum two children. Children follow a specific property : left child of node will be smaller and right child will be greater than node. For example, below tree is a binary search tree.

insert node in binary search tree

Where as this one is not. Why?

insert a node in binary search tree

This specific property of binary search tree helps us solve many problems on binary search tree. As whatever is true for entire BST is also true for left as well as right subtree, we can use recursion to arrive at the solution. Second, divide and conquer can be easily applied as left and right subtrees are exclusive sets and based on requirements, we can easily discard one of it or solve problem separately for left and right subtree and then combine solutions to come to solution for entire tree.

How coming to our first task : How to insert node in binary search tree?

There are two cases: Either tree is empty and this is the first node being inserted. Well, it’s simplest case, allocate node and return it.

Second case is when there is a tree and new node is inserted in it. Here, we have to first find right place where new node should be inserted and then link it with it’s parent’s left or right child.

Algorithm to insert node in binary search tree

1. Check if there is a root node. That means tree is not empty.
2. Now, check value to be inserted is less than root? 
   2.1 If yes, move down to left child. 
   2.2 If no, move down to right child. 
3. Repeat step 2 till you cannot go further down, that means even if value is less than currentNode, but there is no left child or value is greater than current node but there is no right child.  
4. Allocate a new node with given value. 
5. Set left or right pointer in the last node which was not null to point to new node.

Let’s take an example and see what does this algorithm do? We have to insert a new node with value 18.

insert node in binary search tree

First, we check that root is not null. Check if new value is less or greater than current node i.e 30. It is less, so move to left child. Again, left child is not null, check if new value is less or greater than current node’s value i.e 20. It is less than move to left child which is 15. Again check, in this case value to be inserted is greater than current node value. So move down to right child. At this point there is no right child of 10, hence we allocate a new node with value 12 and set right child of 10 to point to new node.

Implementation wise, it’s pretty simple. At each node, we are either discarding it’s left or right subtree and continuing the same problem of insertion of node in one of the subtree. So can be easily implemented using recursion. All we need to take care is of termination condition, which is very easy. Whenever, subtree passed is empty, create a node and return it. The parent node should take care of assigning correct pointer to point to this node.

struct node{
	int value;
	struct node *left;
	struct node *right;
};
typedef struct node Node;
 
 
Node *createNode(int value){
	Node * newNode =  (Node *)malloc(sizeof(Node));
	newNode->value = value;
	newNode->right= NULL;
	newNode->left = NULL;
 
	return newNode;
}
Node *addNode(Node *node, int value){
	if(node == NULL){
		return createNode(value);
	}
	else{
		if (node->value > value){
			node->left = addNode(node->left, value);
		}
		else{
			node->right = addNode(node->right, value);
		}
	}
	return node;
}
/* Driver program for the function written above */
int main(){
	Node *root = NULL;
	//Creating a binary tree
	root = addNode(root,30);
	root = addNode(root,20);
	root = addNode(root,15);
	root = addNode(root,25);
	root = addNode(root,40);
	root = addNode(root,37);
	root = addNode(root,45);
 
	return 0;
}

Complexity insertion algorithm in binary search tree is O(N). It’s usual misconception that complexity of insertion in BST is O(log N). Insertion complexity is O(log N) when binary search tree is balanced. In case BST is completely skewed, worst case complexity becomes O(N).

We can use this insert method to create an entire binary search tree from scratch. Complexity of creating a BST with N nodes will be O(N2). Why?

Please let me know in case there is something wrong or missing. Sharing is caring.

For more linked lists problems : Linked list problems

Path with given sum in binary search tree

Paths with given sum in binary search tree

In last post, we discussed how to print all paths of a tree.  Today let’s discuss another problem which can be used with same method as print all paths in tree with slight various. Problem at hand is to print path with given sum in binary search tree. For example, in given tree below, path with sum 114 is 30,40,45

path with given sum in binary search tree

Basic algorithms remains same as to print paths in a tree. Extra thing to be done is to keep track of sum of all nodes in path leading to current node.  At each node, check if sum of all nodes in path is equal to given number, if yes, print the path. If sum of all nodes at currentNode is greater than sum, then just abandon the path as there is no way that path be the one we are looking for.

Paths with given sum in BST

1. Start from root, call it currentNode.
2. Subtract currentNode value from given sum, call it subSum
3. If sumSum is zero and node is leaf, print the path.
4. Check if subSum is less than zero, if yes, break
5. Else, 
   5.1 Check all path in left subtree of currentNode with sum as subSum
   5.2 Check all paths in right subtree of currentNode with sum as subSum

This algorithm can easily be implemented using recursion. Pass current sum required with each successive node in path. And of course, book-keeping to print the path as we did with printing all paths of a tree.

Path with given sum implementation

Since we are traversing each node at least once, complexity of algorithm to print paths with given sum in binary search tree is O(N).

There is simpler version of this problem : Find if binary search tree contains path with given sum. In this problem, all what is ask is yes or no. No book keeping required.

At each node, subtract node value from sum required, and check if there is path on left or right subtree with reduced sum. Of yes, return yes, if not, then return no. This is classic case of recursion.

Complexity of  implementation of to find if there is a path of given sum in binary search tree also is O(N).

Please share if there is something is wrong or missing. We would love to hear what you have to say.

Inorder predecessor in binary search tree

Inorder predecessor

In last post we discussed inorder successor of a node in binary search tree. In today’s post, we will discuss another similar problem known as finding inorder predecessor of a node in BST.

What is inorder predecessor?

Going by symmetry with inorder successor, inorder predecessor of a node is node which comes just before it in inorder traversal of binary search tree. In other words, it’s the largest node prior to node.

inorder predecessor

For example in tree above, inorder predecessor of 25 is 20; for 37, it’s 30.

One way to find inorder predecessor is to traverse tree inorder and store nodes in an array. While predecessor is asked, just search for node in array and return node just prior to it. Since inorder traversal of a BST puts all nodes in sorted order, we can use binary search algorithm to find given node. However, drawback of this approach is use of extra memory and re-traversals if tree changes frequently.

Instead of traversing entire tree, can we use some kind of information we used while solving inorder successor problem. There are two conditions which will decide inorder predecessor of a node.

  1. If node has left subtree, then maximum element in that left subtree will be output.
  2. If node does not have left subtree, then node at which last right turn was taken is output. 

If node is left most node of tree, then there is no inorder predecessor as there will no right turn taken and there is no left subtree either, hence we should return null.

This is exact opposite of what we did for inorder successor, kind of symmetrical. Let’s take some examples and see if this algorithm works or not? In tree below, find predecessor of 8. Last right turn we took was at 6, and there is no left subtree of 8, hence the answer is 6.
inorder predecessor example
What is predecessor of 10 in inorder traversal of tree?  In this case there is a left subtree for node. Hence, find maximum in left subtree. Maximum node in BST is right most node of tree. Here, maximum of left subtree of 10 is 8, hence answer will be 8.
inorder predecessor implementation

Inorder predecessor implementation

#include<stdio.h>
#include<stdlib.h>
 
struct node{
    int value;
    struct node *left;
    struct node *right;
};
typedef struct node Node;
 
/* This function return the maximum node in tree 
rooted at node root */
Node *findMaximum(Node *root){
    if(!root)
        return NULL;
 
    while(root->right) root = root->right;

    return root;
}

/* 
This function implements the logic described in 
algorithm to find inorder predecessor of a given node
*/
Node *inorderPredecessor(Node *root, int K){
 
    Node *predecessor 	= NULL;
    Node *current  	= root;
 
    if(!root)
        return NULL;
 
    while(current && current->value != K){
        /* 
         Else take left turn and no need to 
         update predecessor pointer 
        */
        if(current->value >K){
            current= current->left;
        }
        /* 
           If node value is less than the node which 
           are looking for, then go to right sub tree
           Also when we move right, update the predecessor
           pointer to keep track of last right turn 
       */
        else{
            predecessor = current;
            current = current->right;
        }
    }
    /*
      Once we reached at the node for which inorder 
      predecessor is to be found,check if it has left 
      sub tree, if yes then find the maximum in that 
      right sub tree and return that node, Else last 
      right turn taken node is already stored in 
      predecessor pointer and will be returned
    */
    if(current && current->left){
        predecessor = findMaximum(current->left);
    }

    return predecessor;
}

Node * createNode(int value){
  Node *newNode =  (Node *)malloc(sizeof(Node));
 
  newNode->value = value;
  newNode->right= NULL;
  newNode->left = NULL;
 
  return newNode;
 
}
 
Node * addNode(Node *node, int value){
  if(!node){
      return createNode(value);
  }
  else{
     if (node->value > value){
        node->left = addNode(node->left, value);
      }
      else{
        node->right = addNode(node->right, value);
      }
  }

  return node;
}
 
/* Driver program for the function written above */
int main(){
  Node *root = NULL;

  //Creating a binary tree
  root = addNode(root,30);
  root = addNode(root,20);
  root = addNode(root,15);
  root = addNode(root,25);
  root = addNode(root,40);
  root = addNode(root,37);
  root = addNode(root,45);
 
  Node *predecessor = inorderPredecessor(root, 40);
  printf("\n Inorder successor node is : %d ",
            predecessor ? predecessor->value: 0);
 
  return 0;
}

Complexity of finding inorder predecessor would be same as inorder successor i.e. O(logN).

Please leave a comment if you find something wrong or not clear enough, I will update. Remember sharing is caring. You can share this post anywhere you like with buttons given below.

Replace node with sum of left and right subtree

Replace node with sum of left and right subtree

Today’s problem is to replace node with sum of left and right subtree below node. By sum of children, we mean sum of all children of node and not just it’s immediate left and right child.
For example, consider binary search tree below,
replace node with sum of left and right subtree

Output should be as

replace node with sum of children
Replaced nodes. Resultant tree

Do you see the pattern here? What should be done before we process a parent node? Yes, we must process it’s left and right child first. And that’s post order traversal of tree. All we need to do is to replace print statement with addition of two nodes. Also, make sure we return sum of left, right and node itself, as parent node of current node will require that.

Algorithm to replace node with sum of left and right subtree

1. Start with root node. 
2. If root is null return zero. 
3. If there is left child, replace left child with sum of its children. 
4. If there is right child, replace right child with sum of its children. 
5. Replace root with sum of its right and left child.
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
 
struct node{
	int value;
	struct node *left;
	struct node *right;
};
typedef struct node Node;
 
int replaceNodeWithSumOfChildren(Node *root){
	if (!root)
		return 0;
	int leftSum =  replaceNodeWithSumOfChildren(root->left);
	int rightSum = replaceNodeWithSumOfChildren(root->right);
 
	if(leftSum + rightSum != 0){
		root->value = leftSum + rightSum;
	}
	return root->value;
}
 
void inorderTraversal(Node * root){
	if(!root)
		return;
 
	inorderTraversal(root->left);
	printf("%d ", root->value);
	inorderTraversal(root->right);
}
Node *createNode(int value){
	Node * newNode =  (Node *)malloc(sizeof(Node));
	newNode->value = value;
	newNode->right= NULL;
	newNode->left = NULL;
 
	return newNode;
}
Node *addNode(Node *node, int value){
	if(node == NULL){
		return createNode(value);
	}
	else{
		if (node->value > value){
			node->left = addNode(node->left, value);
		}
		else{
			node->right = addNode(node->right, value);
		}
	}
	return node;
}
 
/* Driver program for the function written above */
int main(){
	Node *root = NULL;
	//Creating a binary tree
	root = addNode(root,30);
	root = addNode(root,20);
	root = addNode(root,15);
	root = addNode(root,25);
	root = addNode(root,40);
	root = addNode(root,37);
	root = addNode(root,45);
 
	replaceNodeWithSumOfChildren(root);
 
	inorderTraversal(root);	
	return 0;
}

This implementation of replacing node with sum of left and right subtree requires to visit every node of the tree, hence complexity of algorithm is O(N).

Please share if there is something is wrong or missing. If you are interested in contributing to website or have an interview experience to share, please contact us and you can earn money too.

Mirror binary search tree C implementation

Mirror binary search tree

Mirror Binary Search Tree means, left child of each node becomes right child and vice-a-versa. Resultant tree be a tree which will be seen in mirror image of given BST. To understand basics about binary search tree, please refer : insert in BST, search in BST

mirror binary search tree
Original tree
mirror a binary search tree example
Mirrored tree

Algorithm to mirror binary search tree

There are two approaches to this problem. First is to swap data of left and right child of each node. In this approach, it is mandatory to solve this problem bottom up because we must swap children nodes before parent node is swapped with it’s sibling.

Another approach is to swap the pointers themselves. That mean left pointer now start pointing to right child and right pointer to left child. Here, there is  no strict requirement that you need to mirror children before parent node, because pointers themselves are swapped and left and right will anyway be pointing to entire right and left subtree children respectively. Even if you change left child of node to right child, entire left sub tree below the node will become right subtree of node. However, in my honest opinion, follow post order approach, which is to mirror children first and then parent node.

And their comes the solution. Process child nodes first and then the parent node. Typical postorder solution. Only change is print statement in post order traversal will  be replaced by swapping of nodes.

To mirror a BST, we need to again start from the leaves. We first swap the lower most nodes, then move up till  the root.

1. Start with root node. 
2. If root is null return.
3. If there is left child, then mirror the left subtree
4. If there is right child, then mirror the right sub tree. 
5. Swap left and right child.

Mirror binary search tree implementation

Complexity of recursive implementation to mirror a binary search tree is O(n) as each node of tree is traversed at least once.

Please share if something is wrong or missing. Sharing is caring. If you are interested in contributing to website, please contact us.

Diameter of binary tree Recursive implementation

Diameter of binary tree

We all know about height of a binary tree. Diameter of binary tree is closely related to height of it. Problem statement is: Given a binary tree, find diameter of binary tree. Diameter of binary tree is maximum distance between any two nodes in tree. Path between two such nodes may or may not pass through root of the tree. For example, diameter of following trees will be 4 and 7 as shown

diameter of binary tree examplediameter of binary tree

Find diameter of binary tree

As I said in start diameter is closely related to height of binary tree. If Diameter includes root node, then diameter is summation of height of left sub tree and right sub tree plus one for root. If diameter does not include root, then diameter is either diameter of left sub tree or right sub tree.

At any given node, check if diameter of any subtree below tree is greater than sum of height go left subtree, right subtree plus 1. If that is the case, diameter of entire tree remains diameter of that subtree, else change diameter to height of left subtree + height of high subtree +1. Actual expression of diameter of a tree at rooted any given node is

MAX(height(left subtree) + height(right subtree)h+1,
     MAX(diameter of left subtree,diameter of right subtree ));

Starting with leaf nodes we traverse up the tree and pass diameter value for each node to parent node. At parent node, decide whether to include this node based on above mentioned condition.

Algorithm to find diameter of binary tree

1. Start from root
2. If there is left child of node, find diameter of left child.
3. If there is right child, find diameter of right child.
4. Find height of left sub tree.
5. Find height of right sub tree.
6. Return maximum of 1 plus height of left sub tree plus height of right sub tree,  diameter of left sub tree, diameter of right sub tree.

Diameter of binary tree implementation

Since each node of tree will be traversed, complexity of algorithm to find diameter of binary tree will be O (N) where N is number of nodes in tree.
Please share if there is something wrong or missing. If you are interested in contributing to website, please contact us and earn for yourself.

N-ary tree implementation in C

N-ary tree : Way to store hierarchical data

Till now we have learned about binary tree and binary search tree. There is one more form of tree that is N-ary tree or N-ary data structure. As name suggests, Nary tree is a tree where each node has N children. Advance implementations of Nary trees can have flexibility of having different N for each node of the tree. The tree which we will implement will be one such tree. Figure below shows N-ary tree

n-ary tree
Nary tree

What are the usage or applications of N-ary tree or N-ary data structure? One application is to store hierarchical information such as organization charts, store inventories, comments threads with replies etc.
Let’s see how node of a n-ary tree looks like:

 

In this definition, there is one void pointer representing data, this allows us to use the same tree for various data types. Close of C++ template class. In this pointer we put the data information. After that there is one integer nChildren which tells how many children this node has. And in the last we have a pointer to pointer which is nothing but array of pointers to all the children of this node.

Create a node in N-ary tree?

To create a node, we need to pass two parameters. One the number of child nodes this node has. If we don’t know, we can always send 0, later we will see how we can append a child to a parent node. Second is pointer to the data.  Create node function looks like:

Pointer to data, for example an employee record, can be created as follows.

Delete N-ary tree

Deletion of tree happens in similar fashion as for binary tree, delete the children first and then the parent node. In Nary tree we will have multiple child nodes, so we have to go through all the nodes one by one and delete them. Once all child nodes are deleted, delete the parent node. Code to delete a tree is below

Append a child in N-ary tree

To append a child node of a parent node, we need to insert pointer of child to parent array of it’s children, However, we have already allocated the array for the parent node based on input provided at the time of creation of node. How can we increase that? There is one function in C called as realloc which takes two parameters, the old pointer and the size to allocated. It returns the new pointer with new size. Most of the time, the new pointer pointer points to the same memory location and old is done away with. However it is not necessary. New pointer may be pointing to a completely new memory location. So be safe and copy all information from old to new location using memcpy.
We will use this realloc function to reallocate our children array and at the end of the array, add the new child. Code is shown below.

Delete a child

To delete a node, we need to find it. Scan through tree and find the node in parent node’s children array. Delete node’s entry from children array of it’s parent.

Before deleting node, clarify with interviewer or requirement gatherer, what happens to children of current node. If children  have to move to parent node of current, then do that before deleting the node.

If children have to be deleted with node, then recursively delete tree rooted at current node using method mentioned under ‘How to delete a n-ary tree?’

It is costly operation to search a node in N-ary tree. To improve search, we maintain a hash which keeps track of pointer of each node based on same key value. Whenever we want to delete a node, just take pointer from hash and delete it. Similarly, while insertion of a node also, use hash to locate parent pointer.

Update a child in N-ary tree

Using hash mentioned before, locate node pointer, update information by adding new node in children array of parent. Simple!

To print a N-ary tree in level order

No big deal here, it is same as binary search tree level order traversal. Use queue and for node visited, add all children of it on to queue. Take out next node from queue. Repeat process till queue is not empty. Level order traversal of N-ary tree implementation.

 

Above n-ary tree structure can be used to represent organizational structure where an employee can be CEO, MANAGER or EMPLOYEE. CEO is at the first level, MANAGER at the second layer and EMPLOYEE at last layer. Figure shows the layout of Nary tree for organizational tree:

n-ary tree implementation

So this is about N-ary tree, use it wherever you want to store hierarchical data.

Please share if there is something wrong or missing. If you are interested in contributing to website or have an interview experience to share, please contact us.

Postorder traversal without recursion

Postorder traversal without recursion

We discussed inorder traversal without recursion and preorder traversals without recursion earlier. Now let’s focus on postorder traversal without recursion, which is most complex of three tree traversals. In post order traversal of binary tree, left and right children are visited before parent node. For example, post order traversal of below tree is :3,8,6,11,17,15,10

postorder traversal without recursion

Before continuing discussion on non-recursive implementation of post order traversal, understand how is it implemented with recursion.

Postorder traversal Recursive implementation

void postorder(Node *root){
     if(root){
          postorder(root->left);
          postorder(root->right);
          printf("%d", root->data);
     }
}

Looking at code, it is clear that parent node is visited twice, once coming up from left sub tree and second time when coming up from right sub tree. However, parent node is to be printed when we have already printed left as well as right child. So, we need to keep track of the previous visited node.
There are tree values possible for previous node:
1. Previous node is parent of current node, that means we are traversing tree downwards.  No need to do anything with the current node.
2. Previous node is left child of current node, that means we have already visited left child, but still not have visited right child, hence we move to right child of current node.
3. Previous node is right child of current node, left and right child of current node are already visited, hence all we need to do is to print current node.

Postorder traversal without recursion algorithm

1.Start with the root node and push the node onto stack.
2 Repeat all steps till stack is not empty. 
3.Peek the top of the stack. 
  3.1 If previous node is parent of current node : ( When we are moving down the tree)
    3.1.1 If left child is present, push left child onto stack. 
    3.1.2 Else if right child is present, push right child onto stack
    3.1.3 If left and right children are not present, print the node. 
  3.2 If previous node is left child of current node ( When moving up after visiting left node)
    3.2.1 If right child is not present, print current node
    3,2.2 If right child is present, push it onto stack. 
  3.3 If previous node is right child of current node ( When moving up after visiting right child )
    3.3.1 Print the node. 
    3.3.2 Pop node from stack.

Below figure explains execution of postorder traversal algorithm

postorder traversal without recursion implementationpostorder traversal without recursion

Postorder traversal without recursive implementation

#include <stdio.h>
#include<stdlib.h>
#include<math.h>
 
struct node{
	int value;
	struct node *left;
	struct node *right;
};
typedef struct node Node;
 
#define STACK_SIZE 10
 
typedef struct stack{
        int top;
        Node *items[STACK_SIZE];
}stack;
 
void push(stack *ms, Node *item){
   if(ms->top < STACK_SIZE-1){
       ms->items[++(ms->top)] = item;
   }
   else {
       printf("Stack is full\n");
   }
}
 
Node * pop (stack *ms){
   if(ms->top > -1 ){
       return ms->items[(ms->top)--];
   } 
   else{
       printf("Stack is empty\n");
   }
}
Node * peek(stack ms){
  if(ms.top < 0){
      printf("Stack empty\n");
      return 0;
   }
   return ms.items[ms.top];
}
int isEmpty(stack ms){
   if(ms.top < 0) return 1;
   else return 0;
}
 
void postorderTraversalWithoutStack(Node *root){
    stack ms;
    ms.top = -1;

    if(!root) return ;
 
    Node *currentNode = NULL ;
    push(&ms,root);
    Node *prev = NULL;
 
    while(!isEmpty(ms)){
        currentNode = peek(ms);
        /* case 1. We are moving down the tree. */
        if(!prev || prev->left == currentNode || prev->right == currentNode){
			if(currentNode->left)
				push(&ms,currentNode->left);
			else if(currentNode->right)
				push(&ms,currentNode->right);
			else {
                /* If node is leaf node */
                printf("%d ", currentNode->value);
                pop(&ms);
            }
        }
         /* case 2. We are moving up the tree from left child */
        if(currentNode->left == prev){
            if(currentNode->right)
                push(&ms,currentNode->right);
            else {
                printf("%d ", currentNode->value);
                pop(&ms);
            }
         }
 
        /* case 3. We are moving up the tree from right child */
         if(currentNode->right == prev){
              printf("%d ", currentNode->value);
              pop(&ms);
         }
         prev = currentNode;
      }
 
}
 
void postorder (Node * root){
	if ( !root ) return;
 
	postorder(root->left);
	postorder(root->right);
	printf("%d ", root->value );
}
 
Node * createNode(int value){
    Node * newNode =  (Node *)malloc(sizeof(Node));
    newNode->value = value;
    newNode->right= NULL;
    newNode->left = NULL;

    return newNode;
}

Node * addNode(Node *node, int value){
    if(!node){
    	return createNode(value);
    }
    else{
    	if (node->value > value){
    		node->left = addNode(node->left, value);
    	}
    	else{
    		node->right = addNode(node->right, value);
    	}
    }
    return node;
}
 
/* Driver program for the function written above */
int main(){
        Node *root = NULL;
        //Creating a binary tree
        root = addNode(root,30);
        root = addNode(root,20);
        root = addNode(root,15);
        root = addNode(root,25);
        root = addNode(root,40);
        root = addNode(root,37);
        root = addNode(root,45);
        postorder(root);
        printf("\n");
        postorderTraversalWithoutStack(root);
        return 0;
}

Complexity of postorder traversal of binary search tree is O(n) because each node of tree is visited at least one.
Please share if there is something is wrong or missing. If you are interested in contributing to website or an interview experience to share, please contact us.