The question
Given a binary tree, check whether it’s a binary search tree or not.
My solution
I cheated a little in this question because I didn’t remember what a binary search tree is. After checking wikipedia I found the characteristic of a BST:
– The left subtree of a node contains only nodes with keys less than the node’s key.
– The right subtree of a node contains only nodes with keys greater than the node’s key.
– The left and right subtree each must also be a binary search tree.
– Each node can have up to two successor nodes.
– There must be no duplicate nodes.
At the beginning I fell in the trap of going through every node and checking that it was greater than the left and lower than the right but as wikipedia shows. There are scenarios when this simple check wouldn’t work. With this in mind I came with a solution that even though is O(n), it is probably a little convoluted:
– Create a function(isBst)
– The function will return false if the node doesn’t correspond to a BST.
– The function will return either the highest number found in the given node if true was passed in the second argument, or the lowest if there was no second argument.
– Call the function with the root of the tree you want to check
– If the root is null return null
– Create a variable(right) and assign the lowest value on the right node(isBst(root.right))
– Create a variable(left) and assign the highest value on the left node(isBst(root.left, true))
– If right is lower than root or left is higher than root then return false
– If higher was passed as a second argument then return right if it is not null, if it is return root
– If higher was not passed as a second argument then return left if it is not null, if it is return root
The best solution
There are two other solutions that are also O(n) but are a little more elegant. One of them consists of passing the max and min allowed values every time we call isBst. The simplest one seems to consist of traversing the three in order and verifying that the values are output in order.
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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
/*
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13
*/
var bst = {
val: 8,
left: {
val: 3,
left: {
val: 1,
left: null,
right: null
},
right: {
val: 6,
left: {
val: 4,
left: null,
right: null
},
right: {
val: 7,
left: null,
right: null
}
}
},
right: {
val: 10,
left: null,
right: {
val: 14,
left: {
val: 13,
left: null,
right: null
},
right: null
}
}
};
/*
20
/ \
10 30
/ \
5 40
*/
var bt = {
val: 20,
left: {
val: 10,
left: null,
right: null
},
right: {
val: 30,
left: {
val: 5,
left: null,
right: null
},
right: {
val: 40,
left: null,
right: null
}
}
};
// My solution
// Returns false if the root doesn't belong to a BST, otherwise it returns
// if higher is true: the value of the right node
// if higher is not true: the value of the left node
function isBst(root, higher) {
if (root === null) {
return null;
}
var right = isBst(root.right);
if (right === false) {
return false;
}
var left = isBst(root.left, true);
if (left === false) {
return false;
}
if ((right === null || root.val < right) && (left === null || root.val > left)) {
var returnVal;
if (higher) {
returnVal = right === null ? root.val : right;
} else {
returnVal = left === null ? root.val : left;
}
return returnVal;
} else {
return false;
}
}
// Min and max
function isBst2(root, min, max) {
if (min === undefined) {
min = Number.NEGATIVE_INFINITY;
}
if (max === undefined) {
max = Number.POSITIVE_INFINITY;
}
if (root === null) {
return true;
}
if (min > root.val || max < root.val) {
return false;
}
return isBst2(root.left, min, root.val) && isBst2(root.right, root.val, max);
}
// Traverse
function isBst3(root, lastNode) {
if (lastNode === undefined) {
lastNode = Number.NEGATIVE_INFINITY;
}
if (root === null) {
return true;
}
if (!isBst3(root.left, lastNode)) {
return false;
}
if (root.val < lastNode) {
return false;
}
return isBst3(root.right, root.val);
}
function test() {
if (isBst(bst) !== false && isBst(bt) === false &&
isBst2(bst) === true && isBst2(bt) === false &&
isBst3(bst) === true && isBst3(bt) === false) {
console.log('success');
}
}
test(); // Prints success
computer_science algorithms javascript programming