tree reversal

[denver2020]

I am trying to write a recursive function that reverse the actual tree by modifying it rather than creating another one. Below is my code so far.

Below is example before reversal.
			8			
		/		\		
	/				\	
	5				7	
/		\		/		\
1		2		4		6

Below is the example after reversal.

			8			
		/		\		
	/				\	
	7				5	
/		\		/		\
6		4		2		1


typedef struct BinyNode {
  int val;
  struct BinyNode *left;
  struct BinyNode *right;
}BinyNode;


void reverseTree(BinyNode *root) {
        if (root == null) {
             return;
        }
	else
	{ 
	        struct BinyNode* temp; 
                reverseTree(root->left); 
		reverseTree(root->right);
                temp = root->left; 
		root->left = root->right; 
		root->right = temp; 
	} 
    
  
}

void displaytree(BinyNode* root) 
{ 
	if (root == NULL) 
		return; 
	
	displaytree(root->left); 
	cout << root->val << " "; 
	displaytree(root->right); 
} 

[seeplus]

Well the first problem is that reverseTree() has a void return, but is actually returning a value!!

Are you using c or C++ ?

[denver2020]

I use C++ here.

#include <iostream> 
using namespace std; 

typedef struct BinyNode {
  int val;
  struct BinyNode *left;
  struct BinyNode *right;
}BinyNode;


void reverseTree(BinyNode *root) {
        if (root == NULL) {
             return;
        }
	else
	{ 
	        struct BinyNode* temp; 
                reverseTree(root->left); 
		reverseTree(root->right);
                temp = root->left; 
		root->left = root->right; 
		root->right = temp; 
	} 
    
  
}

void displaytree(BinyNode* root) 
{ 
	if (root == NULL) 
		return; 
	
	displaytree(root->left); 
	cout << root->val << " "; 
	displaytree(root->right); 
} 

int main() 
{ 

   displaytree(root);
   reverseTree(root);
   return 0; 
}

[kbw]

The algorithm looks ok, but as @seeplus mentioned, you'll have syntax errors.

Is it the syntax errors you need help with?

[denver2020]

I need to avoid creating new node here. Is there any other way to do it?

#include <iostream> 
using namespace std; 

typedef struct BinyNode {
  int val;
  struct BinyNode *left;
  struct BinyNode *right;
}BinyNode;


struct BinyNode* newBinyNode(int val) 
{ 
	BinyNode* root = new BinyNode;
	root->val = val; 
	root->left = NULL; 
	root->right = NULL; 
	
	return(root); 
} 

void reverseTree(BinyNode *root) {
        if (root == NULL) {
             return;
        }
	else
	{ 
	        struct BinyNode* temp; 
                reverseTree(root->left); 
		reverseTree(root->right);
                temp = root->left; 
		root->left = root->right; 
		root->right = temp; 
	} 
    
  
}

void displaytree(BinyNode* root) 
{ 
	if (root == NULL) 
		return; 
	
	displaytree(root->left); 
	cout << root->val << " "; 
	displaytree(root->right); 
} 

int main() 
{ 
   struct BinyNode *root = newBinyNode(2); 
	root->left = newBinyNode(1); 
	root->right = newBinyNode(4); 
	root->right->left = newBinyNode(3); 
	root->right->right = newBinyNode(5);
        displaytree(root);
        reverseTree(root);
        cout << endl;
        displaytree(root);
        return 0; 
}

[JLBorges]

If dynamic memory allocation must be avoided:

#include <iostream>
#include <iomanip>
#include <algorithm>

struct node
{
    int value = 0 ;
    node* left = nullptr ;
    node* right = nullptr ;
};

std::ostream& print_inorder( const node* root, std::ostream& stm = std::cout )
{
    if(root)
    {
        print_inorder( root->left, stm ) ;
        stm << std::setw(5) << root->value ;
        print_inorder( root->right, stm ) ;
    }
    return stm ;
}

node* reverse( node* root )
{
    if(root)
    {
        reverse(root->left) ;
        reverse(root->right) ;
        using std::swap ;
        swap( root->left, root->right ) ;
    }
    return root ;
}

int main()
{
    node n1{1}, n2{2}, n4{4}, n6{6}, n5{ 5, &n1, &n2 }, n7{ 7, &n4, &n6 }, n8{ 8, &n5, &n7 } ;
    node* root = &n8 ;
    print_inorder(root) << '\n' ;
    print_inorder( reverse(root) ) << '\n' ;
}

https://coliru.stacked-crooked.com/a/097c1a4a30060c75

Another option would be to represent the tree as an array. https://webdocs.cs.ualberta.ca/~holte/T26/tree-as-array.html

[denver2020]

Here actual input must be 8571246 and the expected output must be 8756421. But your code outputs the below: 6 7 4 8 2 5 1, for the below input 1 5 2 8 4 7 6

[keskiverto]

Lets have:

			8			
		/		\		
	/				\	
	5				7	
/		\		/		\
1		2		4		6

What output do you expect from it?
8571246 or 1528476?

[seeplus]

The first issue is actually displaying the tree in the required format - as this is by Level Order traversal - rather than the more usual infix/postfix/prefix format. Consider:

#include <iostream>
#include <utility>
#include <queue>

struct Node {
	int data {};
	Node *left {}, *right {};

	Node(int d) : data(d) {}

	~Node() {
		delete left;
		delete right;
	}
};

std::ostream& printLevelOrder(const Node* root, std::ostream& stm = std::cout) {
	if (root) {
		std::queue<const Node*> q;

		for (q.push(root); !q.empty(); ) {
			const auto node { q.front() };

			stm << node->data << ' ';
			q.pop();

			if (node->left)
				q.push(node->left);

			if (node->right)
				q.push(node->right);
		}
		stm << '\n';
	}

	return stm;
}

Node* reverse(Node* root) {
	if (root) {
		reverse(root->left);
		reverse(root->right);
		std::swap(root->left, root->right);
	}

	return root;
}

int main() {
	auto root { new Node(8) };

	root->left = new Node(5);
	root->right = new Node(7);
	root->left->left = new Node(1);
	root->left->right = new Node(2);
	root->right->left = new Node(4);
	root->right->right = new Node(6);

	std::cout << "By Level Order traversal:\nOriginal\n";
	printLevelOrder(root);

	std::cout << "Reversed\n";
	printLevelOrder(reverse(root));

	delete root;
}

By Level Order traversal:
Original
8 5 7 1 2 4 6
Reversed
8 7 5 6 4 2 1

[denver2020]

Thanks a lot seeplus. This thread is solved and I am closing it. Thanks a lot everyone for your suggestions.