Converting Binary Tree to Doubly Linked List

1. If left subtree exists, process the left subtree
…..1.a) Recursively convert the left subtree to DLL.
…..1.b) Then find inorder predecessor of root in left subtree (inorder predecessor is rightmost node in left subtree).
…..1.c) Make inorder predecessor as previous of root and root as next of inorder predecessor.
2. If right subtree exists, process the right subtree (Below 3 steps are similar to left subtree).
…..2.a) Recursively convert the right subtree to DLL.
…..2.b) Then find inorder successor of root in right subtree (inorder successor is leftmost node in right subtree).
…..2.c) Make inorder successor as next of root and root as previous of inorder successor.
3. Find the leftmost node and return it (the leftmost node is always head of converted DLL)

	#include<iostream>
	#include<queue>
	#include<map>
	#include<climits>
	#include<stack>
	#include<stdio.h>
	using namespace std;
	struct node{
	int data;
	struct node* left;
	struct node* right;
	};
	struct node* newNode(int data){
	struct node* node=new(struct node);
	node->data=data;
	node->left=node->right=NULL;
	return node;
	}
	struct node* insert(struct node* node,int data){
	if(node==NULL)
	return (newNode(data));
	if(data<=node->data)
	node->left=insert(node->left,data);
	else
	node->right=insert(node->right,data);
	return node;
	}
	node* binToList(node* root){
	if(root==NULL)
	return root;
	if(root->left!=NULL){
	node* left;
	left=binToList(root->left);
	for(;left->right!=NULL;left=left->right);
	left->right=root;
	root->left=left;
	}
	if(root->right!=NULL){
	node* right;
	right=binToList(root->right);
	for(;right->left!=NULL;right=right->left);
	root->right=right;
	right->left=root;
	}
	return root;
	}
	node* convertToDLL(node* root){
	if(root==NULL)
	return root;
	root=binToList(root);
	for(;root->left!=NULL;root=root->left);
	return root;
	}
	int main(){
	struct node* root=NULL;
	root=insert(root,4);
	root=insert(root,2);
	root=insert(root,5);
	root=insert(root,1);
	root=insert(root,3);
	node* list=convertToDLL(root);
	for(;list!=NULL;list=list->right)
	cout<<list->data<<" ";
	}

view raw BSTToDLL.cpp hosted with ❤ by GitHub

Thanks to geeksforgeeks for providing such an awesome approach

given a binary tree and two nodes, how do you check if there exist a path between them from the root

Do a preorder traversal

if you find anyone of the node then find the other node in the subtree whose root is the first found node.

	bool isPresent(node* node,int n){
	if(node==NULL)
	return false;
	if(node->data==n)
	return true;
	return isPresent(node->left,n)||isPresent(node->right,n);
	}
	bool isBothNodesinSamePathFromRoot(node* node,int n1,int n2){
	if(node==NULL)
	return false;
	if(node->data==n1)
	return isPresent(node,n2);
	if(node->data==n2)
	return isPresent(node,n1);
	return isBothNodesinSamePathFromRoot(node->left,n1,n2)||isBothNodesinSamePathFromRoot(node->right,n1,n2);
	}

view raw isBothNodesinSamePathFromRoot.cpp hosted with ❤ by GitHub

Maximum complete level of a binary tree

Given a binary tree, find the maximum level at which tree is completely filled.

	int getMaxCompleteLevel(node* node){
	if(node==NULL||!(node->left)||!(node->right))
	return 0;
	int l=getMaxCompleteLevel(node->left);
	int r=getMaxCompleteLevel(node->right);
	return 1+min(l,r);
	}

view raw getMaxCompleteLevel.cpp hosted with ❤ by GitHub

Converting a BST into sorted linked list

This problem requires the inorder traversal of the tree and then subsequently converting the nodes to lists. Below is the code for this problem:

[gist https://gist.github.com/niviusha/5993176]

Post order predecessor of a binary tree

[gist https://gist.github.com/vishnujayvel/5888828]

Printing the ancestors of a node in binary tree

In this tree the ancestors of 4 are 5,10

There is a simple recursive solution to find the ancestor of a binary tree

[gist https://gist.github.com/vishnujayvel/5888810 ]

Inorder traversal of BST without recursion

We all know how easy it is to print bst in inorder traversal using recursion.

What if we want to do this without recursion?

Its not difficult.Recursion uses stacks implicitly while executing.So lets use stacks itself.

algorithm:

1) keep on traversing the root left pushing each node into the stack.

2)if stack is empty exit the function

3)When reaching end pop an element and print it and make root=root->right .Goto step1

	void nonRecursiveInorderTraversal(node *root){
	stack<node*> s;
	cout<<endl;
	while(1){
	while(root){
	s.push(root);
	root=root->left;
	}
	if(s.empty())
	break;
	root=s.top();
	s.pop();
	cout<<root->data<<" ";
	root=root->right;
	}
	}

view raw

inorder

hosted with ❤ by GitHub