-
Notifications
You must be signed in to change notification settings - Fork 6
Expand file tree
/
Copy pathbinarysearchTree_2.cpp
More file actions
129 lines (105 loc) · 2.96 KB
/
binarysearchTree_2.cpp
File metadata and controls
129 lines (105 loc) · 2.96 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
//construction of binary search tree
template <typename T>
class BinaryTreeNode
{
public:
T data;
BinaryTreeNode* left;
BinaryTreeNode* right;
BinaryTreeNode(T data){
this->data=data;
left=NULL;
right=NULL;
}
~BinaryTreeNode(){
delete left;
delete right;
}
};
//taking input
BinaryTreeNode<int>* takeInput(){
int rootData;
cout<<"Enter root data"<<endl;
cin>>rootData;
if(rootData==-1) return NULL;
BinaryTreeNode<int>* root=new BinaryTreeNode<int>(rootData);
BinaryTreeNode<int>* leftChild=takeInput();
BinaryTreeNode<int>* rightChild=takeInput();
root->left=leftChild;
root->right=rightChild;
return root;
}
//printing binary tree
void printTree(BinaryTreeNode<int>* root)
{
if(root==NULL)
return;
cout<<root->data<<":";
if(root->left){
cout<<"L"<<root->left->data<<" ";
}
if(root->right){
cout<<"R"<<root->right->data<<" ";
}
cout<<endl;
printTree(root->left);
printTree(root->right);
}
//sorted array to BST
BinaryTreeNode<int>* sortedArrayToBst(int arr[],int start, int end){
//base case
if (start > end)
return NULL;
int mid = (start+end)/2;
BinaryTreeNode<int>* root = new BinaryTreeNode<int>(arr[mid]);
root->left = sortedArrayToBst(arr,start,mid-1);
root->right = sortedArrayToBst(arr,mid+1,end);
return root;
}
//finding the path between the nodes of a bst
vector<int>* getRootToNodePath(BinaryTreeNode<int>* root, int data){
if(root==NULL)
return NULL;
//root agar null hua to seedhe null return kar denge
//aur agar root me hi data hua then root ke data ko vector me push krke
//return kr denge
if(root->data == data){
vector<int>* output = new vector<int>();
output->push_back(root->data);
return output;
}
//if root me data nhi hua to then ek baar right me and ek baar left me search krenge
vector<int>* leftOutput = getRootToNodePath(root->left,data);
if(leftOutput!=NULL){
leftOutput->push_back(root->data);
return leftOutput;
}
vector<int>* rightOutput = getRootToNodePath(root->right,data);
if(rightOutput!=NULL){
rightOutput->push_back(root->data);
return rightOutput;
}else{
return NULL;
}
}
// 1 2 3 4 5 6 7 -1 -1 -1 -1 8 9 -1 -1 -1 -1 -1 -1
int main()
{
/* array to bst
int arr[]={1,2,3,4,5,6,7};
int n = sizeof(arr)/sizeof(arr[0]);
BinaryTreeNode<int>* root = sortedArrayToBst(arr,0,n);
printTree(root);
*/
BinaryTreeNode<int>* root = takeInput();
vector<int>* output = getRootToNodePath(root,8);
for(int i=0;i<output->size();i++){
cout<<output->at(i)<<endl;
}
delete root;
return 0;
}