Binary Search Tree Validity

Write a function to determine whether a given binary tree of distinct integers is a
valid binary search tree. Assume that each node contains a pointer to its left child, a
pointer to its right child, and an integer, but not a pointer to its parent. You may use
any language you like.
Good Answer: Note that it’s not enough to write a recursive function that just checks
if the left and right nodes of each node are less than and greater than the current
node (and calls that recursively). You need to make sure that all the nodes of the
subtree starting at your current node are within the valid range of values allowed by
the current node’s ancestors. Therefore you can solve this recursively by writing a
helper function that accepts a current node, the smallest allowed value, and the
largest allowed value for that subtree. An example of this is the following (in Java):

   1: boolean isValid(Node root) {

   2: return isValidHelper(root, Integer.MIN_VALUE,

   3: Integer.MAX_VALUE);

   4: }

   5: boolean isValidHelper(Node curr, int min, int max) {

   6: if (curr.left != null) {

   7: if (curr.left.value < min ||

   8: !isValidHelper(curr.left, min, curr.value))

   9: return false;

  10: }

  11: if (curr.right != null) {

  12: if (curr.right.value > max ||

  13: !isValidHelper(curr.right, curr.value, max))

  14: return false;

  15: }

  16: return true;

  17: }

The running time of this algorithm is O(n).

Advertisements

Test Case Methodologies

EP = Equivalence Partitioning. As an example, if you have a range of valid values, like 1-10, you would choose to test one valid value (say 7), and one invalid value (like 0).

BVA = Boundary Value Analysis. If you take the example above, you would test the minimum and maximum boundaries (1 and 10), and test beyond both boundaries (0 and 11). Boundary Value Analysis can be applied to a field, record, file, or anything with a stated or implied limit of some kind.

CE= Cause/effect. This is normally input of a combination of conditions (cause) in order to yield a single system result or transformation (effect). For example, you might want to test the ability to add a customer using a particular screen. This may involve entering multiple fields, such as name, address, and phone number, followed by pressing the “add” button. This is the “cause” portion of the equation. Once you press the “add” button, the system will return a customer number and add the customer to the database. This is the “effect”.

EG = Error guessing. This is when the test analyst uses their knowledge of the system and ability to interpret specifications to “guess” at what type of input might yield an error. For example, perhaps the spec says “the user must enter a code”. The test analyst will think “what if I don’t enter a code?”, “what if I enter the wrong code?”, and so on. This is error guessing.

ECP = Equivalence Class Partitioning – A software testing technique that involves identifying a small set of representative input values that invoke as many different input conditions as possible.

Test Strategy Vs Test Plan

Test Strategy :
A test strategy is a statement of the overall approach to testing, identifying what levels of testing are to be applied and the methods, techniques and tools to be used. A test strategy should ideally be organization wide, being applicable to all of organizations software developments.The application of a test strategy to a software development project should be detailed in the projects software quality plan.
The next stage of test design, which is the first stage within a software development project, is the development of a test plan. A test plan states what the items to be tested are, at what level they will be tested, what sequence they are to be tested in, how the test strategy will be applied to the testing of each item, and describes the test environment.
Components in the Test Strategy are as follows:
1. Scope and objective
2. Business issues
3. Roles and responsibilities
4. Communication and status reporting
5. Test deliverability
6. Test approach
7. Test automation and tools
8. Testing measurements and metrices
9. Risks and mitigation
10. Defect reporting and tracking
11. Change and configuration management
12. Training plan
Test Plan :
A Test Plan describes the approach, Features to be tested, Testers assigned, and whatever you plan for your project. A Test Plan is usually prepared by Manager or Team Lead. That is true but not exclusively. It depends on what the test plan is intended for. Some companies have defined a test plan as being what most would consider a test case. Meaning that it is for one part of the functionality validation.
A test plan may be project wide, or may in fact be a hierarchy of plans relating to the various levels of specification and testing:
• An Acceptance Test Plan, describing the plan for acceptance testing of the software. This would usually be published as a separate document, but might be published with the system test plan as a single document.
• A System Test Plan, describing the plan for system integration and testing. This would also usually be published as a separate document, but might be published with the acceptance test plan.
• A Software Integration Test Plan, describing the plan for integration of testes software components. This may form part of the Architectural Design Specification.
• Unit Test Plan(s), describing the plans for testing of individual units of software. These may form part of the Detailed Design Specifications.
The objective of each test plan is to provide a plan for verification, by testing the software, that the software produced fulfils the requirements or design statements of the appropriate software specification. In the case of acceptance testing and system testing, this means the Requirements Specification.
Test plan is the freezed document developed from SRS(Specification Requirement Document). After completion of testing team formation and risk analysis, Test Lead is preparing test plan document in term of what to test, how to test, who to test, and when to test.There is one Master Test Plan consists of reviewed Project Test Plan and Phase Test Plan. so there is general talk about Project Test Plan.
Components are as follows:
1. Test Plan id
2. Introduction
3. Test items
4. Features to be tested
5. Features not to be tested
6. Approach
7. Testing tasks
8. Suspension criteria
9. Features pass or fail criteria
10. Test environment (Entry criteria, Exit criteria)
11. Test deliverable
12. Staff and training needs
13. Responsibilities
14. Schedule
15. Risk and mitigation
16. Approach
Conclusion :Test Plan is the Document which deals with the When,What and Who will do the Project and Test Strategy is the document which deals with the How to do the project, In case if i wrong anywhere kindly give the feedback.
Why does software have bugs?
1. understanding or no communication – understand the application requirements.
2. Software complexity – the complexity of current software applications can be difficult to comprehend for anyone without experience in modern-day software development.
3. Programming errors – programmers “can” make mistakes.
4. Changing requirements – A redesign, rescheduling of engineers, effects on other projects, etc. If there are many minor changes or any major changes, known and unknown dependencies among parts of the project are likely to interact and cause problems, and the complexity of keeping track of changes may result in errors.
5. Time pressures – scheduling of software projects is difficult at best, often requiring a lot of guesswork. When deadlines loom and the crunch comes, mistakes will be made.
6. Poorly documented code – it’s tough to maintain and modify code that is badly written or poorly documented that result as bugs.
7. Software development tools – various tools often introduce their own bugs or are poorly documented, resulting in added bugs.

Methods of Black box Testing

Graph Based Testing Methods:
Each and every application is build up of some objects. All such objects are identified and graph is prepared. From this object graph each object relationship is identified and test cases written accordingly to discover the errors.

Error Guessing:
This is purely based on previous experience and judgment of tester. Error Guessing is the art of guessing where errors can be hidden. For this technique there are no specific tools, writing the test cases that cover all the application paths.

Boundary Value Analysis:
Many systems have tendency to fail on boundary. So testing boundry values of application is important. Boundary Value Analysis (BVA) is a test Functional Testing technique where the extreme boundary values are chosen. Boundary values include maximum, minimum, just inside/outside boundaries, typical values, and error values.

Extends equivalence partitioning
Test both sides of each boundary
Look at output boundaries for test cases too
Test min, min-1, max, max+1, typical values

BVA techniques:
1. Number of variables
For n variables: BVA yields 4n + 1 test cases.
2. Kinds of ranges
Generalizing ranges depends on the nature or type of variables
Advantages of Boundary Value Analysis
1. Robustness Testing – Boundary Value Analysis plus values that go beyond the limits
2. Min – 1, Min, Min +1, Nom, Max -1, Max, Max +1
3. Forces attention to exception handling

Limitations of Boundary Value Analysis
Boundary value testing is efficient only for variables of fixed values i.e boundary.

Equivalence Partitioning:
Equivalence partitioning is a black box testing method that divides the input domain of a program into classes of data from which test cases can be derived.

How is this partitioning performed while testing:
1. If an input condition specifies a range, one valid and one two invalid classes are defined.
2. If an input condition requires a specific value, one valid and two invalid equivalence classes are defined.
3. If an input condition specifies a member of a set, one valid and one invalid equivalence class is defined.
4. If an input condition is Boolean, one valid and one invalid class is defined.

Comparison Testing:
Different independent versions of same software are used to compare to each other for testing in this method.