Tag Archives: trees

Codeforces #247 (Div.2) C.K-Tree

0
Posted on by

Problem link: http://codeforces.com/contest/431/problem/C

Simple recursion with memoization works.

Code is self explanatory

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <climits>
#include <stdlib.h>
#include <stdio.h>
using namespace std;
#define REP(i,n) for(int i=0; i<n; i++)
#define FOR(i,st,end) for(int i=st;i<end;i++)
#define db(x) cout << (#x) << " = " << x << endl;
#define mp make_pair
#define pb push_back
#define mod 1000000007
typedef long long int ll;
int k,d,n;
ll dp[105][2];
ll solve(int x,int f){
if(dp[x][f]!=-1){
return dp[x][f];
}
if(x>n)
dp[x][f]=0;
else if((x==n)&&f)
dp[x][f]=1;
else{
ll ret=0;
for(int i=1;i<=k;i++){
if(x+i<=n){
ret+=solve(x+i,f||(i>=d)?1:0);
ret%=mod;
}
}
dp[x][f]=ret;
}
return dp[x][f];
}
int main(){
REP(i,105){
dp[i][0]=-1;
dp[i][1]=-1;
}
scanf("%d%d%d",&n,&k,&d);
ll ret=0;
for(int i=1;i<=k;i++){
ret+=solve(i,(i>=d)?1:0);
ret%=mod;
}
cout<<ret;
}
view raw k-tree.cpp hosted with ❤ by GitHub

Converting Binary Tree to Doubly Linked List

0
Posted on by

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

0
Posted on by

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