Question

Create a random binary tree and verify BST property and AVL balance condition. Do not hard code the tree inside the code.

Java or C++ are the options.

Answer 1

Ans:

A BST is a node based binary tree which has the following properties:
• The left subtree of a parent node contains only nodes which is less than the Parent node key.
• The right subtree of a parent node contains only nodes which is greater than the Parent node key.
• Both the left and right subtrees must be a binary search trees.

An AVL tree is a self-balancing BST.In an AVL tree, the heights of the child subtrees of any node differ by atmost one position; if at any time they differ by more than one position, rebalancing is needed to be done to obtain the AVL tree properties.

CODE:

//This is a java program to check whether a tree is AVL tree or not
class BSTAVLTreeNode
{
int value;
BSTAVLTreeNode Left;
BSTAVLTreeNode Right;

BSTAVLTreeNode(int k)
{
value = k;
}
}

public class BST_AVL
{
public static boolean isBalanced(BSTAVLTreeNode root)
{
int Lh; /* left subtree height */
int Rh; /* right subtree height */

if (root == null)
return true;

Lh = height(root.Left);
Rh = height(root.Right);

if (Math.abs(Lh - Rh) <= 1 && isBalanced(root.Left)
&& isBalanced(root.Right))
return true;

return false;
}
public static boolean isBST(BSTAVLTreeNode node)
{
return (isBSTUtil(node, 0, 100));
}

public static boolean isBSTUtil(BSTAVLTreeNode node, int min, int max)
{

if (node == null)
return true;

if (node.value < min || node.value > max)
return false;

return (isBSTUtil(node.Left, min, node.value - 1) && isBSTUtil(
node.Right, node.value + 1, max));
}

public static int height(BSTAVLTreeNode node)
{
if (node == null)
return 0;

return 1 + max(height(node.Left), height(node.Right));
}
  
public static int max(int a, int b)
{
return (a >= b) ? a : b;
}


public static void main(String args[])
{
BSTAVLTreeNode t1 = new BSTAVLTreeNode(3);
t1.Left = new BSTAVLTreeNode(5);
t1.Right = new BSTAVLTreeNode(6);
t1.Right.Left = new BSTAVLTreeNode(7);
t1.Right.Right = new BSTAVLTreeNode(8);

BSTAVLTreeNode t2 = new BSTAVLTreeNode(17);
t2.Left = new BSTAVLTreeNode(7);
t2.Right = new BSTAVLTreeNode(22);
t2.Right.Left = new BSTAVLTreeNode(20);
t2.Right.Right = new BSTAVLTreeNode(25);
t2.Left.Left = new BSTAVLTreeNode(6);
t2.Left.Right = new BSTAVLTreeNode(8);

if (isBST(t1) && isBalanced(t1))
System.out.println("t1 TREE is an AVL tree");
else
System.out.println("t1 TREE is not an AVL tree");

if (isBST(t2) && isBalanced(t2))
System.out.println("t2 TREE is an AVL tree");
else
System.out.println("t2 TREE is not an AVL tree");
}
}

OUTPUT: