Subscribe to:
Post Comments (Atom)

skip to main |
skip to sidebar
"Gebo" means to "give and take". This is my attempt to share the knowledge & experience with the community. Focus on Puzzles, Algorithms, Problem Solving, Java & other Technical Discussions.

## About Me

## Labels / Tag

Subscribe to:
Post Comments (Atom)

algorithms
(15)
amazon
(3)
antivirus
(1)
arithmetic series
(1)
array
(5)
backtracking
(1)
bash
(1)
basics
(1)
binary trees
(1)
brindavan garden
(1)
bulb
(1)
C++
(1)
callback
(1)
clam
(1)
clamav
(1)
clock
(1)
CLRS
(2)
cormen
(3)
data structures
(1)
duplicate
(1)
easymock
(1)
education
(1)
excel
(1)
freshclam
(1)
hanoi
(1)
hashing
(1)
httpclient
(1)
humor
(1)
induction
(1)
interview question
(9)
irrational
(1)
Java
(5)
jmockit
(1)
learning
(1)
level_easy
(1)
linux
(3)
logger
(1)
macro
(1)
madhur
(2)
mathematics
(5)
matrix
(1)
microsoft
(6)
mock
(2)
mockito
(2)
mysore
(1)
networking
(1)
OCW
(1)
odd man out
(1)
oocalc
(1)
OOTB
(1)
pattern
(1)
Persistent
(1)
probability
(2)
problem
(1)
problem solving
(17)
proxy
(1)
proxy selector
(1)
puzzle
(5)
quote
(1)
randomized
(1)
recurrsion
(2)
repeating
(1)
resolution
(1)
reverse
(1)
riddle
(5)
road trip
(1)
script
(1)
search
(2)
shell
(1)
shell script
(1)
socks
(1)
solaris
(1)
solved
(1)
sort
(3)
stock
(1)
strategy
(1)
subversion
(1)
summation
(1)
svn
(1)
switch
(1)
tanwani
(2)
TDD
(2)
technology
(2)
theorem
(1)
timer
(1)
todo
(1)
travel
(1)
trees
(1)
tutorial
(1)
unimodal
(1)
unit test
(2)
walk the bridge
(1)
warmup
(1)
water jugs
(1)
windows
(1)
xkcd joke
(1)

## 4 comments:

Two solutions :

1.> (mine) post order traversal, get max from left tree and min from right tree. Ensure curr > (max from left) and curr < (min from right). do this for all nodes in recursion

2.> (colleague) inorder traversal - the traversal should not break sorted order if this is a BST.

bool isBST(struct node *root) {

if (root == NULL) return true;

if (root->left && maxVal(root->left) > root->data) return false;

if (root->right && minVal(root->right) < root->dasta) return false;

return true;

}

@Madan

Though the solution is perfect, the running time would not be so good.

I suppose those could be improved as well with extra logic though.

The advantage i see of the post-order approach over this one is that the min & max values can be thrown up to the root node, where the check is to be made - so memory usage is O(1) and running time is not affected

I think the best way would be to do inorder traversal of the tree and when the element visited has a value less than the previous one, declare it as not a BST.

Time - O(n)

Space - O(1)

Post a Comment