CareerCup

Do a In order traversal push all the leaf nodes to the queue.

During pop assign the right pointer of the node to the next node.

TC : O(n) and SC : O(n)

#include<iostream>
using namespace std;

class TreeNode{
  public:
	TreeNode* left;
	TreeNode* right;
    int val;
	TreeNode(int);
};

TreeNode::TreeNode( int value ) {
	left = NULL;
	right = NULL;
	val = value;
}

void customInorderTraversal(TreeNode *node , TreeNode **prevleaf){

	if(node->left == NULL && node->right == NULL){
		if(*(prevleaf) != NULL){
			(*(prevleaf))->right = node;
		}
		*(prevleaf) = node;
	}else if(node->left == NULL){
		customInorderTraversal(node->right,prevleaf);	
	}else if(node->right == NULL){
		customInorderTraversal(node->left,prevleaf);	
	}else{
		customInorderTraversal(node->left,prevleaf);
		customInorderTraversal(node->right,prevleaf);	
	}
}

void createTree(TreeNode* node){
	TreeNode* h;
    h = node;
    h->left = new TreeNode(2);
	h->right = new TreeNode(3);
    h->left->left = new TreeNode(4);
	h->left->right = new TreeNode(5);
	h->right->left = new TreeNode(6);
	h->right->right = new TreeNode(7);
	h->left->left->left = new TreeNode(8);
	h->left->left->right = new TreeNode(9);
}

void displayLeafs(TreeNode * rootnode){
	TreeNode* root = rootnode;
	while(root->left != NULL){
		cout<<root->val<<" ";
		root = root->left;
	}
	cout<<"\n Leaf Path : ";
	while(root != NULL){
		cout<<root->val<<" ";
		root = root->right;
	}
}

int main(){
	TreeNode* rootnode = (TreeNode*) new TreeNode(1);
    cout<<" Root : "<<rootnode->val;
    createTree(rootnode);
	TreeNode* prev = NULL;
	customInorderTraversal(rootnode,&prev);
	displayLeafs(rootnode);
	
}

Space complexity O(1). TimeComplexity O(n)

Traverse the tree in-order, while keeping track of the last encountered leaf node. During the traversal, set the right of last encountered leaf-node to the next encountered leaf-node.

Time-complexity : O(n)
Space-complexity : O(height-of-tree)

public static void populateRightOfLeaves(Node root) {
		populateRightOfLeaves(root, null);
	}

	private static Node populateRightOfLeaves(Node root, Node prev) {
		
		if (root == null) {
			return prev;
		}
		
		if (root.left() == null && root.right() == null) { // if leaf
			if (prev != null) {
				prev.setRight(root);
			}
			return root;
		}
		
		prev = populateRightOfLeaves(root.left(), prev);
		return populateRightOfLeaves(root.right(), prev);
	}

int fun(struct node *root)
{
int l,r;
static int flag=0;
static struct node *head = NULL;

if(root == NULL)
{
return 0;

}
l = fun(root->right);
r = fun(root->left);

if((l ==0) && (r ==0))
{
if(flag ==0)
{
flag =1;
head = root;
//printf("\n first head = %d\n", head->data);
}
else
{
root->right = head;
//printf("\n head = %d\n", root->data);
head = root;
}
return 1;
}
else
return 1;
}

void SetLeafRight(struct Node *&node,struct Node *&prev)
{
if(!node)
return;
SetLeafRight(node->left,prev);
SetLeafRight(node->right,prev);
if(!node->left && !node->right)
{
if(prev)
prev->right=node;
prev=node;
prev->right=NULL;
}
}

do reverse inorder traversal

void SetLeafRighttonextLeaf(struct Node *node)
{
static struct Node * next = NULL;
if(!node)
return;
SetLeafRight(node->right);
if(node->left == NULL && node->right == NULL)
{
node->right = next;
next = node;
}
SetLeafRight(node->left,prev);
}
}