Build Tree Postorder and Inorder in c++

 

Tree traversals are an essential concept in computer science and data structures. They are used to traverse and process the elements of a tree in a specific order. In this article, we will discuss two types of tree traversals: postorder and inorder. We will also go over the process of building a tree using postorder and inorder traversals in the C++ programming language.

Postorder Traversal

Postorder traversal is a type of tree traversal where the nodes of a tree are visited in the order of left subtree, right subtree, and then root. This is also known as a depth-first traversal, as it visits all the nodes of a subtree before moving on to the next subtree.

The process of postorder traversal can be broken down into three steps:

1. Traverse the left subtree of the root node.
2. Traverse the right subtree of the root node.
3. Visit the root node.

This process is then repeated for each subtree in the tree.

The C++ code for postorder traversal is as follows:

void postorder(Node* root) { 
 if (root == NULL) { 
 return; 
 }
 postorder(root->left);
 postorder(root->right);
 cout << root->data << " "; 
}

In this code, the function postorder takes a pointer to a node as an argument. The function first checks if the node is NULL, and if it is, it returns. If the node is not NULL, the function then recursively calls itself for the left and right subtrees of the node. Once both subtrees have been traversed, the data of the node is printed.

Inorder Traversal

Inorder traversal is a type of tree traversal where the nodes of a tree are visited in the order of left subtree, root, and then right subtree. This is also a depth-first traversal, as it visits all the nodes of a subtree before moving on to the next subtree.

The process of inorder traversal can be broken down into three steps:

1. Traverse the left subtree of the root node.
2. Visit the root node.
3. Traverse the right subtree of the root node.

This process is then repeated for each subtree in the tree.

The C++ code for inorder traversal is as follows:

void inorder(Node* root) {
 if (root == NULL) {
 return; 
 } 
 inorder(root->left);
 cout << root->data << " "; 
 inorder(root->right);
 }

In this code, the function inorder takes a pointer to a node as an argument. The function first checks if the node is NULL, and if it is, it returns. If the node is not NULL, the function then recursively calls itself for the left subtree of the node. Once the left subtree has been traversed, the data of the node is printed. The function then recursively calls itself for the right subtree of the node.

Building a Tree using Postorder and Inorder Traversals

Building a tree using postorder and inorder traversals is a common problem in computer science and data structures. The process of building a tree using postorder and inorder traversals can be broken down into three steps:

1 Find the root node of the tree in the postorder traversal. 2. Use the inorder traversal to determine the left and right subtrees of the root node.

3. Recursively build the left and right subtrees using the postorder and inorder traversals of the left and right subtrees.

The C++ code for building a tree using postorder and inorder traversals is as follows:

Node* buildTree(int in[], int post[], int inStart, int inEnd, int postStart, int postEnd) {
 // Base case 
 if (inStart > inEnd || postStart > postEnd) {
 return NULL;
 } 
 // Find the root node in the postorder traversal 
 int rootValue = post[postEnd];
 Node* root = new Node(rootValue);
 // Find the index of the root node in the inorder traversal 
 int k = 0;
 for (int i = inStart; i <= inEnd; i++) {
 if (in[i] == rootValue) {
 k = i;
 break;
 }
    } 
 // Recursively build the left and right subtrees
 
    root->left = buildTree(in, post, inStart, k-1, postStart, postStart + k - (inStart + 1));
 root->right = buildTree(in, post, k+1, inEnd, postStart + k - inStart, postEnd - 1);
 return root; 
}

In this code, the function buildTree takes six arguments: the inorder and postorder traversals of the tree, and the start and end indices of the inorder and postorder traversals. The function first checks if the start index is greater than the end index for either the inorder or postorder traversals, and if it is, it returns NULL. This is the base case for the recursion.

The function then finds the root node in the postorder traversal by taking the last element of the postorder traversal. It then creates a new node with the value of the root node and assigns it to the variable root.

Next, the function uses the inorder traversal to find the index of the root node. It then uses this index to determine the start and end indices of the left and right subtrees in the inorder and postorder traversals. The function then recursively calls itself for the left and right subtrees, passing in the appropriate start and end indices for the inorder and postorder traversals. The left and right subtrees are then assigned to the left and right children of the root node, respectively.

Finally, the function returns the root node of the tree.

In conclusion, postorder and inorder traversals are important concepts in computer science and data structures, and building a tree using these traversals is a common problem in the field. By understanding the process and implementing it in C++, you can improve your understanding of tree traversals and data structures as a whole.

Algorithm for building a tree using postorder and inorder traversals:

1. Start by initializing the indices for the inorder and postorder traversals. The inStart and inEnd indices will represent the start and end indices of the inorder traversal, while the postStart and postEnd indices will represent the start and end indices of the postorder traversal.

2. Next, create a base case for the recursion by checking if the inStart index is greater than the inEnd index or the postStart index is greater than the postEnd index. If either of these conditions is true, return NULL.

3. Find the root node in the postorder traversal by taking the last element of the postorder traversal and assign it to a variable rootValue. Create a new node with the value of the root node and assign it to the variable root.

4. Use the inorder traversal to find the index of the root node. Assign this index to the variable k.

5. Determine the start and end indices of the left and right subtrees in the inorder and postorder traversals by using the index k.

6. Recursively call the buildTree function for the left subtree by passing in the inorder and postorder traversals, as well as the appropriate start and end indices for the inorder and postorder traversals of the left subtree. Assign the returned value to the left child of the root node.

7. Recursively call the buildTree function for the right subtree by passing in the inorder and postorder traversals, as well as the appropriate start and end indices for the inorder and postorder traversals of the right subtree. Assign the returned value to the right child of the root node.

8. Return the root node.

9. End

Note:

• The algorithm is a recursive one.
• The time complexity of the algorithm is O(n) as we need to visit all the nodes in the tree once.
• The space complexity of the algorithm is O(n) as we are using