Flatten a Binary Tree in c++

 

Flattening a binary tree in C++ is a common task that can be accomplished using a variety of algorithms. The process of flattening a binary tree involves converting the tree into a linear structure, such as an array or linked list, while preserving the original tree's order. This can be useful in situations where the tree's data needs to be easily accessible in a linear format, such as in a search algorithm or data manipulation.

One common method for flattening a binary tree in C++ is using the pre-order traversal algorithm. The pre-order traversal algorithm visits the root node first, then the left subtree, and finally the right subtree. This method can be implemented using a recursive function, which visits each node in the tree and adds it to the linear structure. The code for this method would look something like this:

void flatten(Node* root, vector<int>& result) {
 if(root == NULL) {
        return;
 }
 result.push_back(root->val);
 flatten(root->left, result); 
 flatten(root->right, result);
 }

In this code, the "result" vector is used to store the flattened tree, and the "flatten" function is called with the root node of the binary tree and the "result" vector. The function first checks if the root node is NULL, and if it is, the function returns. If the root node is not NULL, the value of the root node is added to the "result" vector, and the function is called recursively on the left and right subtrees of the root node.

Another method for flattening a binary tree in C++ is using the in-order traversal algorithm. The in-order traversal algorithm visits the left subtree first, then the root node, and finally the right subtree. This method can also be implemented using a recursive function, which visits each node in the tree and adds it to the linear structure. The code for this method would look something like this:

void flatten(Node* root, vector<int>& result) {
 if(root == NULL) {
 return;
 } 
 flatten(root->left, result);
 result.push_back(root->val);
 flatten(root->right, result); 
}

This code is similar to the previous example, but the order of the recursive calls is different. The function first calls itself on the left subtree, then adds the value of the root node to the "result" vector, and finally calls itself on the right subtree. This results in the tree being flattened in-order.

A third method for flattening a binary tree in C++ is using the post-order traversal algorithm. The post-order traversal algorithm visits the left subtree first, then the right subtree, and finally the root node. This method can also be implemented using a recursive function, which visits each node in the tree and adds it to the linear structure. The code for this method would look something like this:

void flatten(Node* root, vector<int>& result) {
 if(root == NULL) {
 return; 
 } 
 flatten(root->left, result);
     
flatten(root->right, result);
 result.push_back(root->val);
 }

This code is similar to the previous examples, but the order of the recursive calls is

different. The function first calls itself on the left and right subtrees, and then adds the value of the root node to the "result" vector. This results in the tree being flattened in post-order.

It is important to note that while these methods can be used to flatten a binary tree in C++, they all have different time and space complexities. The pre-order and post-order traversal methods have a time complexity of O(n) and a space complexity of O(n), where n is the number of nodes in the tree. The in-order traversal method has a time complexity of O(n) and a space complexity of O(logn), where n is the number of nodes in the tree and log(n) is the height of the tree.

Another method for flattening a binary tree in C++ is using the Morris traversal algorithm. This is an in-order traversal algorithm that uses threading to flatten the tree while traversing it. The Morris traversal algorithm has a time complexity of O(n) and a space complexity of O(1), making it a more efficient option compared to the other methods. The code for this method would look something like this:

void flatten(Node* root) {
    Node* curr = root;
 while(curr != NULL) {
 if(curr->left == NULL) {
 curr = curr->right;
 } 
else {
 Node* pre = curr->left; 
 while(pre->right != NULL) {
 pre = pre->right; 
 } 
 pre->right = curr->right;
 curr->right = curr->left;
 curr->left = NULL;
 curr = curr->right; 
 }
    }
}

In this code, the "curr" variable is used to traverse the tree, and the while loop continues until the entire tree has been traversed. If the current node's left child is NULL, the current node is set to its right child. If the current node's left child is not NULL, a "pre" variable is set to the left child, and the rightmost leaf of the left subtree is found. The right child of the current node is then set to the right child of the "pre" variable, and the left child of the current node is set to its right child. The left child of the current node is then set to NULL, and the current node is set to its right child.

In conclusion, flattening a binary tree in C++ can be accomplished using a variety of algorithms, such as pre-order, in-order, and post-order traversal, as well as the Morris traversal algorithm. Each method has its own time and space complexity, and it is important to consider these factors when choosing which method to use. The Morris traversal algorithm is the most efficient option, with a time complexity of O(n) and a space complexity of O(1). By implementing these algorithms in your C++ code, you can easily flatten binary trees and take advantage of their linear structure for various purposes.