CareerCup

It would be a post order traversal with an additional feature that we'd pass in the root node to the traversal function. In the post-order

process node

step we just point the child node to the root node that we passes earlier.

I'm not sure if I understand the meaning of reversal correctly. In the current scene the reversed tree won't remain a tree, correct??

Can somebody explain the question?

I am assuming the struct of the Tree to be following:

struct Tree
{
  int data;
  int num_children;
  struct Tree** children; //Array of tree pointers to children
}

Tree **output;
static int count;

ReverseTernaryTree(Tree* Root)
{
    output = (Tree**)malloc(sizeof(Tree*)*100); // Assuming there are no more than  100 leaf nodes.
    int i;
    for(i=0;i<Root->num_children;i++)
    {
          Reverse(Root->children[i],Root);
    }
    
}


Reverse(Tree *node, Tree* prev)
{
   if(node.num_children == 0)
   {
       node->children[0] = prev;
       output[count] = node;
       count++;
       return;
   }
   else
   {
      int i=0;
      for(i=0; i<node->num_children; i++)
      {
          Tree* temp = node->children[i];
          node->children[i] = prev;
          Reverse(temp,node);
      }
   }
}

Explanation:

Output contains the list of all the pointers to leaf nodes which point to their parent. So, the entire tree is reversed in place.
Each child node is pointed to its parent and its child is also reversed to point to its parent.

Let's make the problem more clear.

Q:Given a binary tree, reverse tree with following features:
1. For leaf nodes, their left pointers point to their parent, and their right pointers point to other leaves. You have to return a header pointer pointing to the first item in leaf list.
2. For none-leaf nodes, their left pointers point to their parent and their right pointer point to NULL.

Here is code:

typedef struct node {
  int data;
  struct node *left;
  struct node *right;
}Node;

Node *pre = NULL;
Node *head = NULL;

void reverseTree(Node *node, Node *parent){
  if (node == NULL)
    return;

  if (node->left == NULL && node->right == NULL) {
    if (pre == NULL) {
      head = node;
      pre = node;
    } else {
      pre->right = node;
      pre = node;
    }
    node->left = parent;
    return;
  }

  if (node->left != NULL) {
    reverseTree(node->left, node);
  }

  if (node->right != NULL) {
    reverseTree(node->right, node);
  }

  node->left = parent;
  node->right = NULL;
}

What are the leaf nodes ? 89674??? what is Head-> 8->3->6->9->NULL then ?

elementary reversal is to point the child nodes left pointers to the root. you can recurse this by first reversing the subtrees and then the root. working example as below

void reverse(Node* root)
  {
    
       if((root->left==NULL) && (root->right==NULL))
       {
                             cout<<"NULL reached";
                             List.add(root);
         return; }
      
                         
       if(root->left)
       reverse(root->left);
       
       if(root->right)
       reverse(root->right);
       
       cout<<"about to reverse node " << root->data<<endl;
       
       if(root->left)
       {
       root->left->left = root;
        root->left->right  = NULL;
        }
    
   if(root->right){
     root->right->right = root;
    root->right->right = NULL;
    } 
          
   }

@Kshitij .leaf nodes are 8 , 3 , 6 , 9 , head no such things just return list containing leaf node .

can somebody explain the problem? can't catch it.

It seems to me that reversing a Tree is no different from reversing a LinkedList : visit a node, back up the reference to its children list, make it point to its parent and then recurse for each child passing them the current node as a parent.
I don't understand the leaf part though.

1
/ | \
2 3 4
/ / \
5 6 7
/ \
8 9

Post-order... Also assuming that each node has only one parent (ie: can't be reached by multiple node in the original tree).

static List<Node> leafs = new List<Node>();
List<Node> Reverse(Node head, Node parent)
{
	if(head == null) return null;
	
	foreach(Node curr in head.Children)
	{
		Reverse(curr, head);
	}

	if(head.Children.Count == 0)
		leafs.Add(head);

	head.Children.Clear();

	if(parent != null)
		head.Children.Add(parent);
}

This code will not compile but I think will serve the essence -

struct node
{
	//Data elements
	node* left;
	node* right;
}

void tree_reverse(node* root, node* parent, list<node>& leaves)
{
	if (root == null)
	{
		return;
	}
	else
	{
		if(root->right == null && root->left == null)
		{
			leaves.pushback(*root);
		}
		else
		{
			tree_reverse(root->left, root, list<node> leaves);
			tree_reverse(root->right, root, list<node> leaves);
		}
		root->left = parent; //The left pointer will be used
		root->right = null; // Right would be defunct
	}
}

Call ReverseTTree(root,null).

ReverseTTree(Node node,Node parent){

List list= new List();

int n=node.child.length;
int i=0;

if(n==0){
node.next=parent
node.prev=null;
list.add(node)
return list;
}

while( i<=n){
List li2 = ReverseTTree(node.child[i],node)
for(int j=0;j<li2.size();j++){
Node node1=(Node) li2.get(i);
node1.next=node;
node1.prev=null;
list.add(node1);
}
i++;
}
return list;
}

Please let me know for any bugs...

Hi Gayle,
Can you please provide your thoughts?

Anyone with final, working and Good Solution?