negation in C function

Hi,

I have this sample code:

public static int last_printed = Integer.MIN_VALUE; 2      

public static boolean checkBST(TreeNoden) {

if      (n == null) return true;

// Check / recurse left
if (lcheckBST(n.left)) return false;

// Check current
if (n.data <= last_printed) return false; last_printed = n.data;

// Check / recurse right
if (!checkBST(n.right)) return false;

return true; // All good!
}

My question is what does !checkBST means ... thank you
zizi21Asked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Guy Hengel [angelIII / a3]Billing EngineerCommented:
checkBST  is the (recursive) function, and does return some boolean value (true or false)

! <boolean_expression>  will return the negated value (I assume you know what that means)

if this is clear, does that line still give you some problems understanding it?
0
zizi21Author Commented:
Thanks for replying.

Say, for this line, if (lcheckBST(n.left)) return false;
say checkBST returns true and so ! true is false
or say checkBST returns false and so, !false is true

why are we always returning false then .. (return false)
0
Guy Hengel [angelIII / a3]Billing EngineerCommented:
>why are we always returning false then .. (return false)

we are not ALWAYS returning false. for this general syntax:
IF ( <boolean_expression> )  do_something;

the "do_something" will only be exectued if <boolean_expression> evaluated to true
hence:
if the checkBST returns false, ! false returns true,  => RETURN FALSE
if the checkBST returns true, ! true returns false  => go to the next line
0
Cloud Class® Course: Ruby Fundamentals

This course will introduce you to Ruby, as well as teach you about classes, methods, variables, data structures, loops, enumerable methods, and finishing touches.

frankhelkCommented:
Looks like that's a function to parse some binary tree to search for a value.

n seems to be an object with at least 3 properties:

n.left is a pointer to the next node (or leaf) to the left (whatever that means ...)
n.right is similar to n.left, but to the right side.
(A value of null describes the end of the branch to that side.)
d.data contains some kind of date value.

The function seems to search the entire tree for the maximum value of n.date, which is finally returned in last_printed.

Not elegant (a simple run over an array of objects would be faster and less stressy to the stack), but working.

The line
if (n.data <= last_printed) return false; last_printed = n.data;

Open in new window

is a bit irritating, because the last operation ("last_printed = n.data;") is not in the "if true" path of th if statment ... it will be executed if the condition evaluates to false.
0
sarabandeCommented:
fyi: 'boolean' is not a genuine c type (nor c++ type). however, the boolean could be defined by typedef statement:

typedef int boolean;   // now you can use boolean for int

or by preprocessor definition:

#define boolean int

these statements could be somewhere in an internal header. if you have an editor with the 'go to definition' function provided, you may right-click on 'boolean' type and try to locate the definition.

note, the 'bool' type is only standard for c++. in c you often have BOOL what resolves to an 'int' type.

also 'null'  (small letters) is not genuine and either was  defined by a #define preprocessor statement or as a 'const int' (or as an enumeration constant (less likely).

public static boolean ...
it looks as if the code is java code. that also would explain why the BSTNode was not a pointer (since the members were accessed as n.left and n.right). in managed c++ the the public keyword also could be used with a function, but as far as i know managed c++ doesn't have boolean type.

Not elegant (a simple run over an array of objects would be faster and less stressy to the stack)
actually, a binary tree with nodes pointing to left and right nodes (leafs finally) has some advantages over an array for example when inserting new values. so, elegance is not necessarily a citerion.

if (!checkBST(n.left)) return false;

Open in new window

an equivalent condition to the above is

if (checkBST(n.left) == false)


as Andy has said, the n.left member is a BSTNode pointing to the left child node. since n.left is a pointer it may be NULL (what actually is defined as a 0 integer). so if we ignore that BSTNode was used like a pointer the checkBST was called recursively for the left child node. because of that it returns false if one of the following statements applies:

(1) if (!checkBST(n.left)) return false;   // note it actually is checkBST(n.left.left)
(2) if (n.data <= last_printed) return false;
(3) if (!checkBST(n.right)) return false;  // again: it actually is checkBST(n.left.right)

if a BSTTree was called recursively as it was done in your function it is called a preorder iteration:

assume you have a tree (think of pointers going left-down and right-down) like

                                   8
                     5                         11
            3              7           10         13
       2       4      6            9         12
 1                

then the root node has 8 as data and left node has 5 and right node has 11.

to iterate the tree such that the values give a sorted array, you would go down left nodes until node with 1 was reached which is a leaf. then go back to 3 which has a right node 4, then back to 5 forward until 6 then back to 7, and so on. the call stack when calling checkBST([1]) is:

checkBST([8])          
checkBST([5])
checkBST([3])
checkBST([2])
checkBST([1])

the last one would call checkBST(<null>) since it has a null left node, what returns true because of first statement in checkBST: 'if (n == null) return true;'

then since the last value printed was not greater than 1 (it was Integer.MINVALUE), it doesn't return with false and calls checkBST(n.right) which also returns true cause [1].right is null. hence checkBST([1]) returns true (all good). because of that checkBST([2]) would step to 'check current' and since 1 is less than 2 all is good and it steps to checkBST(n.right) which returns true since it is null. so checkBST[2] also returns true and we come to checkBST([3]) which checks that last value 2 is less than 3 and calls checkBST([4]) for the right node which returns true since [4] is a leaf and last value 3 is less than 4, ...

going on you see the tree was traversed in preorder and in my sample it will finally return true since the values are well defined and the nodes as well. if you change one of the numbers to say number 6 to 20, the checkBST would return false (finally) cause when node [7] was checked the last number was 20 and was not less than 7. same would happen if one of the child nodes was at same level or higher than its parent node. so if one of the checks failed the final return als fails.

the recursive traversion is possible for a tree since each node actually is a subtree and the recursion can stop if we reached a leaf (which is also a subtree though degenerated).

Sara
0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
zizi21Author Commented:
sorry for the late reply as something happened. thank you.
0
frankhelkCommented:
Me:
Not elegant (a simple run over an array of objects would be faster and less stressy to the stack)

sarabande:
actually, a binary tree with nodes pointing to left and right nodes (leafs finally) has some advantages over an array for example when inserting new values. so, elegance is not necessarily a citerion.

Sure. On the other side, the objects need to be stored somewhere ... which might be some kind of array or a collection. To simply find the highest value within such a collection, recursive parsing a binary tree is definitely not the most performant option ... just sweeping tru it (i.e. va an enumertion of the collection) would be much more elegant for that.

Nevertheless the binary tree is useful for managing the connections and hierarchies - and could be used in parallel.
0
Guy Hengel [angelIII / a3]Billing EngineerCommented:
Huh?

  finding the smallest/highest value in a binary tree is VERY efficient, as all you need is to take the left/righ- most node, and you are done. 1+log2(n) steps max, if I remember well the formula. means in short that for a binary tree having 1000 items, you will need something like 10 steps to get the smallest or highest number.
  in a unsorted collection you will need 1000 looping and comparison steps ...

  if the collection is sorted (the how is not the question here), then there you have only 1 step: get the first (or the last) item in the collection. but then, you need to see how the collection is managed (aka how insertions are managed ...), because inserting an item into a regular array is very costful then...
0
sarabandeCommented:
On the other side, the objects need to be stored somewhere ...
bst trees are only transient. if you need storing you would not store the tree but only the data. you easily could recreate the tree from a sorted list. dictionaries and maps typically have a binary tree for their keys.

if you need to store trees such that they could updated, you would have the data separated and build index files for example as hash trees or  bayer trees. the latter have multiple keys and pointers in a so-called bucket. the pointers were pointing to lower level  buckets (normally a 4k record). these buckets are not full such that you normally could add new keys without moving records. in case a bucket becomes full you would insert a new empty bucket and equally divide the entries. if a bucket takes 16 keys you'll get up to 256 keys to level 2 and 65536 keys to level 3. so even for a big amount of keys you only have few records to read for a lookup of a key and pointer to data.

Sara
0
frankhelkCommented:
OK - as far as I understand, the given tree has data ... so there's a list object with the data and some separate tree description object to define the tree ... and to find the most recent date one has to mangle thru all nodes an leafs.

In that scenario I would definitely sweep thru an enumeration of the data list before trying to recursively parsing the tree ... less overhead, less stack stress ... more performance.

I would prefer other things for other tasks, but in that case ...
0
sarabandeCommented:
less overhead, less stack stress ...
granted,

more performance
no. a bst search has log2 performance for a single search what beats sequential search (depending on the complexity of the comparision) already for a few hundred elements. if you need to add keys or update/remove an existing key, the performance benefits may already be significant for less than 100 elements, say if you have strings. for a persistent index sequential search isn't an alternative at all.

note, recursive calls are not a must for traversing a tree. you alway could do it in a while loop as well. but if elegance is a criterion, a good recursive design surely is the winner.

Sara
0
frankhelkCommented:
Hmm - I admit that a bst search is faster if the tree is organized for searching a data item. But the tree in question (as a far as I could see from the initial code) seems not to be ... so the search needs to really see every data item to evaluate the searched value. The given code just does that with recursive tree climbing. In that case I suspect a linear sweep over the list to be more perfomant, too.
0
Guy Hengel [angelIII / a3]Billing EngineerCommented:
fankhelk: the tree there IS sorted.
all nodes to the left of the node have lower values than the node value
all nodes to the right of the node have higher values than the node value

but I concur that this simplistic b-tree is only the low-level version of what databases implement, like sarabande indicated, where on each "node" there are several values (for different reasons, take non-unique indexes for example ...)
0
sarabandeCommented:
also note, the function checkBST is a function to check that the BST tree is valid. it doesn't search for a single value but checks that the tree was in order and has to visit each single node (leaf) because of that.

Sara
0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
C

From novice to tech pro — start learning today.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.