Skip to main content

Check if a binary tree is BST or not in scala

Delete a node in binary search tree

Scala program for Check if a binary tree is BST or not. Here mentioned other language solution.

// Scala program for
// Check if a binary tree is BST or not
class TreeNode(var data: Int,
	var left: TreeNode,
		var right: TreeNode)
{
	def this(data: Int)
	{
		this(data, null, null)
	}
}
class BinaryTree(var root: TreeNode)
{
	def this()
	{
		this(null)
	}
	def isBst(node: TreeNode, 
              l: TreeNode, 
              r: TreeNode): Boolean = {
		if (node != null)
		{
			if (l != null && l.data > node.data || 
                r != null && r.data < node.data)
			{
				// When parent node are not form of binary tree
				return false;
			}
			return (isBst(node.left, l, node) && 
                    isBst(node.right, node, r));
		}
		return true;
	}
	// Display tree elements in order form
	def inorder(node: TreeNode): Unit = {
		if (node != null)
		{
			inorder(node.left);
			// Print node value
			print("  " + node.data);
			inorder(node.right);
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var tree: BinaryTree = new BinaryTree();
		/*
		  Binary Tree
		  ---------------
		          15
		          / \
		         /   \
		        10   24
		       /    /  \
		      9    16   30
		*/
		// Add tree node
		tree.root = new TreeNode(15);
		tree.root.left = new TreeNode(10);
		tree.root.right = new TreeNode(24);
		tree.root.right.right = new TreeNode(30);
		tree.root.right.left = new TreeNode(16);
		tree.root.left.left = new TreeNode(9);
		// Display Tree elements
		tree.inorder(tree.root);
		if (tree.isBst(tree.root, null, null))
		{
			println("\n  Yes ");
		}
		else
		{
			println("\n  No ");
		}
		/*
		  Add new node 25 in binary tree
		  -----------------------
		      15
		      / \
		     /   \
		    10   24
		   /    /  \
		  9    16   30
		         \
		          25
		*/
		tree.root.right.left.right = new TreeNode(25);
		// Display Tree elements
		tree.inorder(tree.root);
		if (tree.isBst(tree.root, null, null))
		{
			println("\n  Yes ");
		}
		else
		{
			println("\n  No ");
		}
	}
}

Output

  9  10  15  16  24  30
  Yes
  9  10  15  16  25  24  30
  No




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment