The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as
well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct. Donald E. Knuth

Tree

Problem :-
Check if a given tree is a Binary Search Tree ( BST ).
The tree shown below is a BST.

Binary Search Tree

Solution :-
We need to validate that properties of BST are satisfied at each of the nodes.
Suppose we start at root node X . If maximum value in the left subtree is less than X -> data and minimum value in the right subtree is greater than X -> data , then BST properties are satisfied and we will recursively validate the properties for other nodes. If all the nodes are validated, then the Binary Tree is a Binary Search Tree .

#include<iostream>
using namespace std;

// node structure
typedef struct tree_node
{
   int value;
   struct tree_node *left, *right;
}node;

// create a new node
node *getNewNode(int value) {
   node *new_node = new node;
   new_node->value = value;
   new_node->left = NULL;
   new_node->right = NULL;
   return new_node;
}

// create the tree
node *createTree() {
   node *root = getNewNode(25);
   root->left = getNewNode(15);
   root->right = getNewNode(30);
   root->left->left = getNewNode(5);
   root->left->right = getNewNode(20);
   root->left->left->left = getNewNode(2);
   root->right->right = getNewNode(40);
   return root;
}

// get the maximum value in a subtree
int getMaxVal(node *temp) {
   while(temp->right != NULL)
      temp = temp->right;
   return temp->value;
}

// get the minimum value in a subtree
int getMinVal(node *temp) {
   while(temp->left != NULL)
      temp = temp->left;
   return temp->value;
}

// checks if the input tree is a BST
bool isBST(node *root) {
   if (root == NULL) return true;
   if (root->left && getMaxVal(root->left) > root->value)
      return false; // BST property violation
   if (root->right && getMinVal(root->right) <= root->value)
      return false; // BST property violation
   if (!isBST(root->left) || !isBST(root->right))
      return false;
   return true;
}

//main
int main() {
   node *root = createTree();
   bool is_bst = isBST(root);
   if (is_bst)
      cout<<"\nInput tree is a BST";
   else
      cout<<"\nInput tree is not a BST";
   cout<<endl;
   return 0;
}

Back | Next

All problems on Trees
* Implement the inorder , preorder and postorder traversal mechanisms of a tree
* Implement an algorithm to insert a node in a Binary Search Tree ( BST )
* Implement an algorithm to find the height of a Binary Tree
* Implement an algorithm to get the level of a node in a Binary Tree assuming root node to be at level 1
* Get the root to leaf path in a Binary Tree such that the sum of the node values in that path is minimum among all possible root to leaf paths
* Print all the ancestors of a given node in a Binary Tree
* Replace all the node values with the sum of the node values of ancestral nodes in a Binary Tree
* Check if the given tree is a sum tree i.e value at each node is equal to the value of all elements in its left subtree and right subtree
* Given a Binary Tree, create another tree which is a mirror image of the given tree
* Construct a tree, given its inorder and preorder traversals
* Find the Least Common Ancestor ( LCA ) of two nodes in a Binary Search Tree
* Find the Least Common Ancestor ( LCA ) of two nodes in a Binary Tree
* Compute the Diameter of a given Binary Tree
* Check if a given tree is a Binary Search Tree ( BST )