some old, but useful tree algorithms

1. in-order traversal to test if a binary search tree


#include<iostream>
#include<stack>

using namespace std;

struct TreeNode
{
int value;
TreeNode* left;
TreeNode* right;
};

bool IsBST(TreeNode* root)
{
stack<TreeNode*> my_stack;
TreeNode* prev=nullptr;
TreeNode* cur_node=root;
while(cur_node || !my_stack.empty())
{
if(cur_node)
{
my_stack.push(cur_node);
cur_node=cur_node->left;
}
else
{
TreeNode* top_node=my_stack.top();
if(prev && top_node->value<=prev->value)
return false;
prev=top_node;
cur_node=prev->right;
my_stack.pop();
}

}
return true;
}

2. a recursive algorithm to test if a binary search tree

#include <stdio.h>

#include <stdlib.h>

#include <limits.h>

/* A binary tree node has data, pointer to left child

   and a pointer to right child */

struct node

{

    int data;

    struct node* left;

    struct node* right;

};

int isBSTUtil(struct node* node, int min, int max);

/* Returns true if the given tree is a binary search tree

 (efficient version). */

int isBST(struct node* node)

{

  return(isBSTUtil(node, INT_MIN, INT_MAX));

}

/* Returns true if the given tree is a BST and its

   values are >= min and <= max. */

int isBSTUtil(struct node* node, int min, int max)

{

  /* an empty tree is BST */

  if (node==NULL)

     return 1;

       

  /* false if this node violates the min/max constraint */ 

  if (node->data < min || node->data > max)

     return 0;

  /* otherwise check the subtrees recursively,

   tightening the min or max constraint */

  return

    isBSTUtil(node->left, min, node->data-1) &&  // Allow only distinct values

    isBSTUtil(node->right, node->data+1, max);  // Allow only distinct values

}


bool IsBST(Node* root,int& mymin,int& mymax)
{
if(!root)
{
mymin=INT_MAX;
mymax=INT_MIN;
return true;
}
int min1,max1,min2,max2;
bool l=IsBST(root->L,min1,max1);
bool r=IsBST(root->R,min2,max2);
mymin=min(min1,min2);
mymin=min(mymin,root->val);
mymax=max(max1,max2);
mymax=max(mymax,root->val);
return l && r && max1<root->val && min2>root->val;
}






check if a tree is balanced







#include<iostream> struct node { int data; struct node* left; struct node* right; }; bool IsBalanced(struct node* root,int& height) { if(root==NULL) { height=0; return true; } int lh,rh; bool l,r; l=IsBalanced(root->left,lh); r=IsBalanced(root->right,rh); height=(lh>rh?lh:rh)+1; if(abs(lh-rh)>=2) return false; else return l&&r; }