-
Notifications
You must be signed in to change notification settings - Fork 1
/
Balanced Binary Tree.cpp
103 lines (94 loc) · 2.13 KB
/
Balanced Binary Tree.cpp
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
#include<iostream>
#include<stdio.h>
using namespace std;
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
//int A[]= {1,2,3,-1,-1,4,-1,-1,5};
struct TreeNode{
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x): val(x), left(NULL), right(NULL){}
};
class Solution {
public:
bool isValidBST(TreeNode *root){
return isValidMaxMin(root, INT_MIN,INT_MAX);
}
public:
bool isValidMaxMin(TreeNode* root, int min ,int max){
if(NULL == root)
return true;
else if(root ->val > min && root ->val < max)
return ( isValidMaxMin(root ->left, min,root -> val)
&& isValidMaxMin(root ->right, root->val, max));
else
return false;
}
public:
TreeNode* createTree(void){
int data;
TreeNode* root;
cin >> data;
if( data == -1)
root = NULL;
else
{
root = (TreeNode*)malloc(sizeof(TreeNode));
root -> val = data;
root -> left = createTree();
root -> right = createTree();
}
return root;
}
public:
void PreOrderTree(TreeNode *T){
if(NULL != T){
PreOrderTree(T -> left);
cout << T -> val << " ";
PreOrderTree(T -> right);
}
}
public:
void InOrderTree(TreeNode *T){
if(NULL != T)
{
cout << T -> val << " ";
InOrderTree(T -> left);
InOrderTree(T -> right);
}
}
public:
void PostOrderTree(TreeNode *T){
if(NULL != T){
PostOrderTree(T -> left);
PostOrderTree(T -> right);
cout << T -> val << " ";
}
}
};
int main()
{
// { 1,2,#,#,3,#,#,4,#,5,#,#,#}
Solution s;
TreeNode* root = s.createTree();
//cout << " PreOrder of the BST is : ";
//s.PreOrderTree(root);
//cout << endl << "InOrder of the BST is: ";
//s.InOrderTree(root);
//cout << endl << "PostOrder of the BST is:";
//s.PostOrderTree(root);
//cout << endl << root->right->left->right->val << endl; //outht to be 5
//cout << root -> left -> val << endl;
cout << " whether it is a valid BST: " << s.isValidBST(root) << endl;
cin.get();
getchar();
return 0;
}