Binary search Tree

mirror()
change a tree so that the roles of the left and right pointers are swapped at every node. so the tree



void mirror(node* root)
{
if(root==null) return
mirror(root->left)
mirror(root->right)
node* temp
temp=root->left
root->left=root->right
root->right=temp
}
sametree()
given two binary trees, return true if they are structurally identical they are made of nodes with the same values arranged in the same way
int sametree(node* root1, node* root2(
{
if(root1==null && root2==null) return true
if(root1!=null && root2!=null(
return((root1->data==root2->data)&&
(sametree(root1->left,root2->left)(
&&sametree(root1->right,root2->right(((
return false
}
binary search tree checking:
this background is used by the next two problems: given a plain binary tree, examine the tree to determine if it meets the requirement to be a binary search tree. to be a binary search tree, for every node, all of the nodes in its left tree must be <= the node, and all of the nodes in its right subtree must be > the node. consider the following four examples




isbst()
suppose you have helper functions minvalue() and maxvalue() that return the min or max int value from a non-empty tree write an isbst() function that returns true if a tree is a binary search tree and false otherwise.
int isbst(node* node)
{
if (node==null) return(true(
if (node->left!=null && minvalue(node->left) > node->data)
return(false)
if (node->right!=null && maxvalue(node->right) <= node->data)
return(false)
return (isbst(node->left) && isbst(node->right))
}

write a c program to create a copy of a tree.
node *copy(node *root)
{
node *temp
if(root==null)return null
temp = new(node)
temp->value = root->value
temp->left = copy(root->left)
temp->right = copy(root->right)
return(temp)
}
deletion
deleting an item from a binary search tree is a little harder than inserting one. before we write any code, let’s consider how to deleting nodes from a binary search tree in an abstract fashion.
here’s a bst from which we can draw examples during the discussion. here, we recognize three distinct cases.



case 1: p has no right child:
it is trivial to deleting a node with no right child, such as node 1, 4, 7, or 8 above. we replace the pointer leading to p by p’s left child. in other words, we replace the deletingd node by its left child. for example, the process of deleting node 8 looks like this:








case 2: p’s right child has no left child:
this case deletings any node p with a right child r that itself has no left child. nodes 2, 3, and 6 in the tree above are examples. for instance, to deleting node 2 in the tree above, we can replace it by its right child 3, giving node 2’s left child 1 to node 3 as its new left child. the process looks like this:








case 3: p’s right child has a left child:
let p’s inorder successor, that is, the node with the smallest value greater than p, be s then, our strategy is to detach s from its position in
the tree, which is always an easy thing to do, and put it into the spot formerly occupied by p, which disappears from the tree. in our example, to deleting node 5, we move inorder successor node 6 into its place, like this:


the code for bst deletion closely follows the above discussion. let’s start with an outline of the function:
step 1: find bst node to deleting .
step 2: deleting bst node .
step 3: finish up after deleting bst node .