Posted on by Kalkicode
Code Binary Tree

Convert binary tree into min max product in kotlin

Change the binary tree into min max product

Kotlin program for Convert binary tree into min max product. Here more solutions.

/*
    Kotlin program for
    Modify the binary tree nodes with min max product
*/
// Binary Tree node
class TreeNode
{
	var data: Int;
	var left: TreeNode ? ;
	var right: TreeNode ? ;
	constructor(data: Int)
	{
		//set node value
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
class Collector
{
	var max: Int;
	var min: Int;
	constructor()
	{
		this.max = 0;
		this.min = 0;
	}
}
class BinaryTree
{
	var root: TreeNode ? ;
	constructor()
	{
		this.root = null;
	}
	// Display tree elements in preorder form
	fun preorder(node: TreeNode ? ): Unit
	{
		if (node != null)
		{
			//Print node value
			print("  " + node.data);
			this.preorder(node.left);
			this.preorder(node.right);
		}
	}
	// Returns a maximum value of given two numbers
	fun max(a: Int, b: Int): Int
	{
		if (a > b)
		{
			return a;
		}
		else
		{
			return b;
		}
	}
	// Returns a minimum value of given two numbers
	fun min(a: Int, b: Int): Int
	{
		if (a < b)
		{
			return a;
		}
		else
		{
			return b;
		}
	}
	// Replace the given binary tree nodes with its min-max product
	fun minMaxProduct(node: TreeNode ? ): Collector ?
	{
		if (node != null)
		{
			// Get current node data
			val x: Int = node.data;
			val info: Collector = Collector();
			if (node.left == null && node.right == null)
			{
				// When leaf node
				info.max = x;
				info.min = x;
				return info;
			}
			var left: Collector ? = this.minMaxProduct(node.left);
			var right: Collector ? = this.minMaxProduct(node.right);
			if (node.left != null && node.right != null)
			{
				// Case A
				// When node have left and right subtree
				// Change node value
				node.data = this.min(left!!.min, right!!.min) * 
                  this.max(right.max, left.max);
				// Update new min and max value
				info.min = this.min(left.min, this.min(right.min, x));
				info.max = this.max(left.max, this.max(right.max, x));
			}
			else if (node.right != null)
			{
				// Case B
				// When node have right subtree
				// Change node value
				node.data = right!!.min * right.max;
				// Update new min and max value
				info.min = this.min(right.min, x);
				info.max = this.max(right.max, x);
			}
			else
			{
				// Case C
				// When node have left subtree
				// Change node value
				node.data = left!!.min * left.max;
				// Update new min and max value
				info.min = this.min(left.min, x);
				info.max = this.max(left.max, x);
			}
			// Return result
			return info;
		}
		return null;
	}
}
fun main(args: Array < String > ): Unit
{
	// New binary tree
	val tree: BinaryTree = BinaryTree();
	/*
	    Construct Binary Tree
	    -----------------------         
	        8
	       / \ 
	      /   \
	     4     9
	    / \   / \
	   7   3 5   2
	      /   \
	     6     7
	        
	*/
	// Add tree node
	tree.root = TreeNode(8);
	tree.root?.left = TreeNode(4);
	tree.root?.left?.right = TreeNode(3);
	tree.root?.left?.left = TreeNode(7);
	tree.root?.right = TreeNode(9);
	tree.root?.right?.left = TreeNode(5);
	tree.root?.right?.right = TreeNode(2);
	tree.root?.left?.right?.left = TreeNode(6);
	tree.root?.right?.left?.right = TreeNode(7);
	println("\n Before ");
	//  Display Tree elements
	tree.preorder(tree.root);
	/*
	    Min Max product
	    -----------------------  
	                  (2 x 9) = 18     
	                     8 
	                   /   \
	                  /     \
	                 /       \
	                /         \ 
	               /           \ 
	       21     /             \     14
	    (3 x 7)  4               9  (2 x 7)
	            / \  36    49   / \
	           7   3(6x6) (7x7)5   2 
	              /             \
	             6               7  
	    -------------------------------
	    Before preorder
	     8    4  7   3  6   9  5  7  2
	    After
	     18  21  7  36  6  14  49  7  2
	        
	*/
	tree.minMaxProduct(tree.root);
	println("\n After ");
	tree.preorder(tree.root);
}

Output

 Before
  8  4  7  3  6  9  5  7  2
 After
  18  21  7  36  6  14  49  7  2

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