Problem

Given a binary tree, find out if it is a binary search tree or not.

Approach 1

• You can traverse the tree in in-order way, and see if the elements are assending.

  • You may either put the elements into an array and see if the array is sorted in assending way,

  • or while traversing see if the current element is always greater than or equal to previous element.

    • return false is current data is less than previously printed data.

    • may use a static variable to hold the last printed value.

• Complete solution can be found @ http://javajee.com/solution-checking-if-a-binary-tree-is-a-binary-search....

Approach 2

• For a BST, all left nodes should be less than or equal to current node and current node must be less than all right nodes.

• We will have a recursive function that checks if this property is true for root node and all its sub trees:

  • If the method get null node, it may return true, and should be first checked (exit condition for the recursion).

  • Check if all left nodes are less than or equal to current node and current node is less than all right nodes

    • Pass current minimum and current data to left subtree

    • Pass current data and current max to right sub trees

• Complete solution can be found @ http://javajee.com/solution-check-if-a-binary-tree-is-a-binary-search-tr....

Note:

• Here, I will giving some of the common approach(es) for the problems on trees and graph given earlier.

• The solutions may not be the best. But it will surely give enough information to start thinking. Convert them into algorithms (or code) to gain best out of these.

• Original list of questions can be found @ http://javajee.com/problems-list-of-problems-on-trees-and-graphs-for-int....