Skip to main content

Find maximum GCD value in binary tree path

Here given code implementation process.

import java.util.ArrayList;
/*
  Java program
  Find maximum GCD value from root to leaf in a binary tree
*/
// Binary Tree node
class TreeNode
{
    public int data;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int data)
    {
        // Set node value
        this.data = data;
        this.left = null;
        this.right = null;
    }
}
public class BinaryTree
{
    public TreeNode root;
    public int result;
    public BinaryTree()
    {
        // Set initial tree root to null
        this.root = null;
        this.result = 0;
    }
  	// Finding gcd of two numbers using recursion
    public int findGCD(int a, int b)
    {
        if (b == 0)
        {
            return a;
        }
        return findGCD(b, a % b);
    }
    // Find all path and detecting maximum gcd of path using recursion
    public void maxGCD(TreeNode node, ArrayList < Integer > path)
    {
        if (node == null)
        {
            return;
        }
        // Add path element
        path.add(node.data);
        if (node.left == null && node.right == null)
        {
            int i = 1;
            // First node of path
            int auxiliary = path.get(0);
            while (i < path.size())
            {
                auxiliary = findGCD(auxiliary, path.get(i));
                i++;
            }
            if (auxiliary > this.result)
            {
                // New largest gcd of current path
                this.result = auxiliary;
            }
        }
        else
        {
            maxGCD(node.left, path);
            maxGCD(node.right, path);
        }
        // Remove last node in path
        path.remove(path.size() - 1);
    }
    // Handles the request of finding maximum gcd in tree path
    public void pathGCD()
    {
        if (this.root == null)
        {
            // Empty Tree
            return;
        }
        else
        {	
          	// This is use to collect sort path
        	ArrayList < Integer > path = new ArrayList < Integer > ();
          	// Reset the resultant gcd
           	this.result = Integer.MIN_VALUE;
          	// Find max gcd in binary tree path
            maxGCD(this.root, path);
          	// Display calculated result
          	System.out.println(" Result : "+this.result);
        }
    }
    public static void main(String[] args)
    {
        // Create new binary tree
        BinaryTree tree = new BinaryTree();
        /*
                 4                            
               /   \    
              20    2    
             / \     \               
            3   5     12
               / \    / \
              6   8  5   8
             /   /    \
            9   3     15 
        
        -----------------
        Constructing binary tree    
        */
        tree.root = new TreeNode(4);
        tree.root.left = new TreeNode(20);
        tree.root.left.right = new TreeNode(5);
        tree.root.left.right.left = new TreeNode(6);
        tree.root.left.right.left.left = new TreeNode(9);
        tree.root.left.right.right = new TreeNode(8);
        tree.root.left.right.right.left = new TreeNode(3);
        tree.root.left.left = new TreeNode(3);
        tree.root.right = new TreeNode(2);
        tree.root.right.right = new TreeNode(12);
        tree.root.right.right.right = new TreeNode(8);
        tree.root.right.right.left = new TreeNode(5);
        tree.root.right.right.left.right = new TreeNode(15);
        // Test case
        // [4 2 12 8] gcd is 2
        tree.pathGCD();
    }
}

input

 Result : 2
// Include header file
#include <iostream>
#include <limits.h>
#include <vector>
using namespace std;

/*
  C++ program
  Find maximum GCD value from root to leaf in a binary tree
*/

// Binary Tree node
class TreeNode
{
	public: 
    int data;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int data)
	{
		// Set node value
		this->data = data;
		this->left = NULL;
		this->right = NULL;
	}
};
class BinaryTree
{
	public: TreeNode *root;
	int result;
	BinaryTree()
	{
		this->root = NULL;
		this->result = 0;
	}
	// Finding gcd of two numbers using recursion
	int findGCD(int a, int b)
	{
		if (b == 0)
		{
			return a;
		}
		return this->findGCD(b, a % b);
	}
	// Find all path and detecting maximum gcd of path using recursion
	void maxGCD(TreeNode *node, vector < int > path)
	{
		if (node == NULL)
		{
			return;
		}
		// Add path element
		path.push_back(node->data);
		if (node->left == NULL && node->right == NULL)
		{
			int i = 1;
			// First node of path
			int auxiliary = path.at(0);
			while (i < path.size())
			{
				auxiliary = this->findGCD(auxiliary, path.at(i));
				i++;
			}
			if (auxiliary > this->result)
			{
				// New largest gcd of current path
				this->result = auxiliary;
			}
		}
		else
		{
			this->maxGCD(node->left, path);
			this->maxGCD(node->right, path);
		}
		// Remove last node in path
		path.pop_back();
	}
	// Handles the request of finding maximum gcd in tree path
	void pathGCD()
	{
		if (this->root == NULL)
		{
			// Empty Tree
			return;
		}
		else
		{
			// This is use to collect sort path
			vector < int > path ;
			// Reset the resultant gcd
			this->result = INT_MIN;
			// Find max gcd in binary tree path
			this->maxGCD(this->root, path);
			// Display calculated result
			cout << " Result : " << this->result << endl;
		}
	}
};
int main()
{
	// Create new binary tree
	BinaryTree *tree = new BinaryTree();
	/*
	         4                            
	       /   \    
	      20    2    
	     / \     \               
	    3   5     12
	       / \    / \
	      6   8  5   8
	     /   /    \
	    9   3     15 

	-----------------
	Constructing binary tree    
	*/
	tree->root = new TreeNode(4);
	tree->root->left = new TreeNode(20);
	tree->root->left->right = new TreeNode(5);
	tree->root->left->right->left = new TreeNode(6);
	tree->root->left->right->left->left = new TreeNode(9);
	tree->root->left->right->right = new TreeNode(8);
	tree->root->left->right->right->left = new TreeNode(3);
	tree->root->left->left = new TreeNode(3);
	tree->root->right = new TreeNode(2);
	tree->root->right->right = new TreeNode(12);
	tree->root->right->right->right = new TreeNode(8);
	tree->root->right->right->left = new TreeNode(5);
	tree->root->right->right->left->right = new TreeNode(15);
	// Test case
	// [4 2 12 8] gcd is 2
	tree->pathGCD();
	return 0;
}

input

 Result : 2
// Include namespace system
using System;
using System.Collections.Generic;
/*
  Csharp program
  Find maximum GCD value from root to leaf in a binary tree
*/
// Binary Tree node
public class TreeNode
{
	public int data;
	public TreeNode left;
	public TreeNode right;
	public TreeNode(int data)
	{
		// Set node value
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
public class BinaryTree
{
	public TreeNode root;
	public int result;
	public BinaryTree()
	{
		// Set initial tree root to null
		this.root = null;
		this.result = 0;
	}
	// Finding gcd of two numbers using recursion
	public int findGCD(int a, int b)
	{
		if (b == 0)
		{
			return a;
		}
		return this.findGCD(b, a % b);
	}
	// Find all path and detecting maximum gcd of path using recursion
	public void maxGCD(TreeNode node, List < int > path)
	{
		if (node == null)
		{
			return;
		}
		// Add path element
		path.Add(node.data);
		if (node.left == null && node.right == null)
		{
			int i = 1;
			// First node of path
			int auxiliary = path[0];
			while (i < path.Count)
			{
				auxiliary = this.findGCD(auxiliary, path[i]);
				i++;
			}
			if (auxiliary > this.result)
			{
				// New largest gcd of current path
				this.result = auxiliary;
			}
		}
		else
		{
			this.maxGCD(node.left, path);
			this.maxGCD(node.right, path);
		}
		// Remove last node in path
		path.RemoveAt(path.Count - 1);
	}
	// Handles the request of finding maximum gcd in tree path
	public void pathGCD()
	{
		if (this.root == null)
		{
			// Empty Tree
			return;
		}
		else
		{
			// This is use to collect sort path
			List < int > path = new List < int > ();
			// Reset the resultant gcd
			this.result = int.MinValue;
			// Find max gcd in binary tree path
			this.maxGCD(this.root, path);
			// Display calculated result
			Console.WriteLine(" Result : " + this.result);
		}
	}
	public static void Main(String[] args)
	{
		// Create new binary tree
		BinaryTree tree = new BinaryTree();
		/*
		         4                            
		       /   \    
		      20    2    
		     / \     \               
		    3   5     12
		       / \    / \
		      6   8  5   8
		     /   /    \
		    9   3     15 

		-----------------
		Constructing binary tree    
		*/
		tree.root = new TreeNode(4);
		tree.root.left = new TreeNode(20);
		tree.root.left.right = new TreeNode(5);
		tree.root.left.right.left = new TreeNode(6);
		tree.root.left.right.left.left = new TreeNode(9);
		tree.root.left.right.right = new TreeNode(8);
		tree.root.left.right.right.left = new TreeNode(3);
		tree.root.left.left = new TreeNode(3);
		tree.root.right = new TreeNode(2);
		tree.root.right.right = new TreeNode(12);
		tree.root.right.right.right = new TreeNode(8);
		tree.root.right.right.left = new TreeNode(5);
		tree.root.right.right.left.right = new TreeNode(15);
		// Test case
		// [4 2 12 8] gcd is 2
		tree.pathGCD();
	}
}

input

 Result : 2
<?php
/*
  Php program
  Find maximum GCD value from root to leaf in a binary tree
*/
// Binary Tree node
class TreeNode
{
	public $data;
	public $left;
	public $right;
	public	function __construct($data)
	{
		// Set node value
		$this->data = $data;
		$this->left = NULL;
		$this->right = NULL;
	}
}
class BinaryTree
{
	public $root;
	public $result;
	public	function __construct()
	{
		$this->root = NULL;
		$this->result = 0;
	}
	// Finding gcd of two numbers using recursion
	public	function findGCD($a, $b)
	{
		if ($b == 0)
		{
			return $a;
		}
		return $this->findGCD($b, $a % $b);
	}
	// Find all path and detecting maximum gcd of path using recursion
	public	function maxGCD($node, $path)
	{
		if ($node == NULL)
		{
			return;
		}
		// Add path element
		$path[] = $node->data;
		if ($node->left == NULL && $node->right == NULL)
		{
			$i = 1;
			// First node of path
			$auxiliary = $path[0];
			while ($i < count($path))
			{
				$auxiliary = $this->findGCD($auxiliary, $path[$i]);
				$i++;
			}
			if ($auxiliary > $this->result)
			{
				// New largest gcd of current path
				$this->result = $auxiliary;
			}
		}
		else
		{
			$this->maxGCD($node->left, $path);
			$this->maxGCD($node->right, $path);
		}
		// Remove last node in path
		array_pop($path);
	}
	// Handles the request of finding maximum gcd in tree path
	public	function pathGCD()
	{
		if ($this->root == NULL)
		{
			// Empty Tree
			return;
		}
		else
		{
			// This is use to collect sort path
			$path = array();
			// Reset the resultant gcd
			$this->result = -PHP_INT_MAX;
			// Find max gcd in binary tree path
			$this->maxGCD($this->root, $path);
			// Display calculated result
			echo(" Result : ".$this->result.
				"\n");
		}
	}
}

function main()
{
	// Create new binary tree
	$tree = new BinaryTree();
	/*
	         4                            
	       /   \    
	      20    2    
	     / \     \               
	    3   5     12
	       / \    / \
	      6   8  5   8
	     /   /    \
	    9   3     15 

	-----------------
	Constructing binary tree    
	*/
	$tree->root = new TreeNode(4);
	$tree->root->left = new TreeNode(20);
	$tree->root->left->right = new TreeNode(5);
	$tree->root->left->right->left = new TreeNode(6);
	$tree->root->left->right->left->left = new TreeNode(9);
	$tree->root->left->right->right = new TreeNode(8);
	$tree->root->left->right->right->left = new TreeNode(3);
	$tree->root->left->left = new TreeNode(3);
	$tree->root->right = new TreeNode(2);
	$tree->root->right->right = new TreeNode(12);
	$tree->root->right->right->right = new TreeNode(8);
	$tree->root->right->right->left = new TreeNode(5);
	$tree->root->right->right->left->right = new TreeNode(15);
	// Test case
	// [4 2 12 8] gcd is 2
	$tree->pathGCD();
}
main();

input

 Result : 2
/*
  Node JS program
  Find maximum GCD value from root to leaf in a binary tree
*/
// Binary Tree node
class TreeNode
{
	constructor(data)
	{
		// Set node value
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
class BinaryTree
{
	constructor()
	{
		this.root = null;
		this.result = 0;
	}
	// Finding gcd of two numbers using recursion
	findGCD(a, b)
	{
		if (b == 0)
		{
			return a;
		}
		return this.findGCD(b, a % b);
	}
	// Find all path and detecting maximum gcd of path using recursion
	maxGCD(node, path)
	{
		if (node == null)
		{
			return;
		}
		// Add path element
		path.push(node.data);
		if (node.left == null && node.right == null)
		{
			var i = 1;
			// First node of path
			var auxiliary = path[0];
			while (i < path.length)
			{
				auxiliary = this.findGCD(auxiliary, path[i]);
				i++;
			}
			if (auxiliary > this.result)
			{
				// New largest gcd of current path
				this.result = auxiliary;
			}
		}
		else
		{
			this.maxGCD(node.left, path);
			this.maxGCD(node.right, path);
		}
		// Remove last node in path
		path.pop();
	}
	// Handles the request of finding maximum gcd in tree path
	pathGCD()
	{
		if (this.root == null)
		{
			// Empty Tree
			return;
		}
		else
		{
			// This is use to collect sort path
			var path = [];
			// Reset the resultant gcd
			this.result = -Number.MAX_VALUE;
			// Find max gcd in binary tree path
			this.maxGCD(this.root, path);
			// Display calculated result
			console.log(" Result : " + this.result);
		}
	}
}

function main()
{
	// Create new binary tree
	var tree = new BinaryTree();
	/*
	         4                            
	       /   \    
	      20    2    
	     / \     \               
	    3   5     12
	       / \    / \
	      6   8  5   8
	     /   /    \
	    9   3     15 

	-----------------
	Constructing binary tree    
	*/
	tree.root = new TreeNode(4);
	tree.root.left = new TreeNode(20);
	tree.root.left.right = new TreeNode(5);
	tree.root.left.right.left = new TreeNode(6);
	tree.root.left.right.left.left = new TreeNode(9);
	tree.root.left.right.right = new TreeNode(8);
	tree.root.left.right.right.left = new TreeNode(3);
	tree.root.left.left = new TreeNode(3);
	tree.root.right = new TreeNode(2);
	tree.root.right.right = new TreeNode(12);
	tree.root.right.right.right = new TreeNode(8);
	tree.root.right.right.left = new TreeNode(5);
	tree.root.right.right.left.right = new TreeNode(15);
	// Test case
	// [4 2 12 8] gcd is 2
	tree.pathGCD();
}
main();

input

 Result : 2
import sys
#  Python 3 program
#  Find maximum GCD value from root to leaf in a binary tree

#  Binary Tree node
class TreeNode :
	def __init__(self, data) :
		#  Set node value
		self.data = data
		self.left = None
		self.right = None
	

class BinaryTree :
	def __init__(self) :
		self.root = None
		self.result = 0
	
	#  Finding gcd of two numbers using recursion
	def findGCD(self, a, b) :
		if (b == 0) :
			return a
		
		return self.findGCD(b, a % b)
	
	#  Find all path and detecting maximum gcd of path using recursion
	def maxGCD(self, node, path) :
		if (node == None) :
			return
		
		#  Add path element
		path.append(node.data)
		if (node.left == None and node.right == None) :
			i = 1
			#  First node of path
			auxiliary = path[0]
			while (i < len(path)) :
				auxiliary = self.findGCD(auxiliary, path[i])
				i += 1
			
			if (auxiliary > self.result) :
				#  New largest gcd of current path
				self.result = auxiliary
			
		else :
			self.maxGCD(node.left, path)
			self.maxGCD(node.right, path)
		
		#  Remove last node in path
		del path[len(path) - 1]
	
	#  Handles the request of finding maximum gcd in tree path
	def pathGCD(self) :
		if (self.root == None) :
			#  Empty Tree
			return
		else :
			#  This is use to collect sort path
			path = []
			#  Reset the resultant gcd
			self.result = -sys.maxsize
			#  Find max gcd in binary tree path
			self.maxGCD(self.root, path)
			#  Display calculated result
			print(" Result : ", self.result)
		
	

def main() :
	#  Create new binary tree
	tree = BinaryTree()
	#         4                            
	#       /   \    
	#      20    2    
	#     / \     \               
	#    3   5     12
	#       / \    / \
	#      6   8  5   8
	#     /   /    \
	#    9   3     15 
	# -----------------
	# Constructing binary tree    
	tree.root = TreeNode(4)
	tree.root.left = TreeNode(20)
	tree.root.left.right = TreeNode(5)
	tree.root.left.right.left = TreeNode(6)
	tree.root.left.right.left.left = TreeNode(9)
	tree.root.left.right.right = TreeNode(8)
	tree.root.left.right.right.left = TreeNode(3)
	tree.root.left.left = TreeNode(3)
	tree.root.right = TreeNode(2)
	tree.root.right.right = TreeNode(12)
	tree.root.right.right.right = TreeNode(8)
	tree.root.right.right.left = TreeNode(5)
	tree.root.right.right.left.right = TreeNode(15)
	#  Test case
	#  [4 2 12 8] gcd is 2
	tree.pathGCD()

if __name__ == "__main__": main()

input

 Result :  2
#  Ruby program
#  Find maximum GCD value from root to leaf in a binary tree
#  Binary Tree node
class TreeNode 
	# Define the accessor and reader of class TreeNode
	attr_reader :data, :left, :right
	attr_accessor :data, :left, :right
	def initialize(data) 
		#  Set node value
		self.data = data
		self.left = nil
		self.right = nil
	end

end

class BinaryTree 
	# Define the accessor and reader of class BinaryTree
	attr_reader :root, :result
	attr_accessor :root, :result
	def initialize() 
		self.root = nil
		self.result = 0
	end

	#  Finding gcd of two numbers using recursion
	def findGCD(a, b) 
		if (b == 0) 
			return a
		end

		return self.findGCD(b, a % b)
	end

	#  Find all path and detecting maximum gcd of path using recursion
	def maxGCD(node, path) 
		if (node == nil) 
			return
		end

		#  Add path element
		path.push(node.data)
		if (node.left == nil && node.right == nil) 
			i = 1
			#  First node of path
			auxiliary = path[0]
			while (i < path.length) 
				auxiliary = self.findGCD(auxiliary, path[i])
				i += 1
			end

			if (auxiliary > self.result) 
				#  New largest gcd of current path
				self.result = auxiliary
			end

		else
			self.maxGCD(node.left, path)
			self.maxGCD(node.right, path)
		end

		#  Remove last node in path
		path.delete_at(path.length - 1)
	end

	#  Handles the request of finding maximum gcd in tree path
	def pathGCD() 
		if (self.root == nil) 
			#  Empty Tree
			return
		else
 
			#  This is use to collect sort path
			path = []
			#  Reset the resultant gcd
			self.result = -(2 ** (0. size * 8 - 2))
			#  Find max gcd in binary tree path
			self.maxGCD(self.root, path)
			#  Display calculated result
			print(" Result : ", self.result, "\n")
		end

	end

end

def main() 
	#  Create new binary tree
	tree = BinaryTree.new()
	#         4                            
	#       /   \    
	#      20    2    
	#     / \     \               
	#    3   5     12
	#       / \    / \
	#      6   8  5   8
	#     /   /    \
	#    9   3     15 
	# -----------------
	# Constructing binary tree    
	tree.root = TreeNode.new(4)
	tree.root.left = TreeNode.new(20)
	tree.root.left.right = TreeNode.new(5)
	tree.root.left.right.left = TreeNode.new(6)
	tree.root.left.right.left.left = TreeNode.new(9)
	tree.root.left.right.right = TreeNode.new(8)
	tree.root.left.right.right.left = TreeNode.new(3)
	tree.root.left.left = TreeNode.new(3)
	tree.root.right = TreeNode.new(2)
	tree.root.right.right = TreeNode.new(12)
	tree.root.right.right.right = TreeNode.new(8)
	tree.root.right.right.left = TreeNode.new(5)
	tree.root.right.right.left.right = TreeNode.new(15)
	#  Test case
	#  [4 2 12 8] gcd is 2
	tree.pathGCD()
end

main()

input

 Result : 2

import scala.collection.mutable._;
/*
  Scala program
  Find maximum GCD value from root to leaf in a binary tree
*/
// Binary Tree node
class TreeNode(var data: Int,
	var left: TreeNode,
		var right: TreeNode)
{
	def this(data: Int)
	{
		// Set node value
		this(data,null,null);
	}
}
class BinaryTree(var root: TreeNode,
	var result: Int)
{
	def this()
	{
		this(null, 0);
	}
	// Finding gcd of two numbers using recursion
	def findGCD(a: Int, b: Int): Int = {
		if (b == 0)
		{
			return a;
		}
		return findGCD(b, a % b);
	}
	// Find all path and detecting maximum gcd of path using recursion
	def maxGCD(node: TreeNode, path: ArrayBuffer[Int]): Unit = {
		if (node == null)
		{
			return;
		}
		// Add path element
		path += node.data;
		if (node.left == null && node.right == null)
		{
			var i: Int = 1;
			// First node of path
			var auxiliary: Int = path(0);
			while (i < path.size)
			{
				auxiliary = findGCD(auxiliary, path(i));
				i += 1;
			}
			if (auxiliary > this.result)
			{
				// New largest gcd of current path
				this.result = auxiliary;
			}
		}
		else
		{
			maxGCD(node.left, path);
			maxGCD(node.right, path);
		}
		// Remove last node in path
		path.remove(path.size - 1);
	}
	// Handles the request of finding maximum gcd in tree path
	def pathGCD(): Unit = {
		if (this.root == null)
		{
			// Empty Tree
			return;
		}
		else
		{
			// This is use to collect sort path
			var path: ArrayBuffer[Int] = new ArrayBuffer[Int]();
			// Reset the resultant gcd
			this.result = Int.MinValue;
			// Find max gcd in binary tree path
			maxGCD(this.root, path);
			// Display calculated result
			println(" Result : " + this.result);
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		// Create new binary tree
		var tree: BinaryTree = new BinaryTree();
		/*
		         4                            
		       /   \    
		      20    2    
		     / \     \               
		    3   5     12
		       / \    / \
		      6   8  5   8
		     /   /    \
		    9   3     15 
		-----------------
		Constructing binary tree    
		*/
		tree.root = new TreeNode(4);
		tree.root.left = new TreeNode(20);
		tree.root.left.right = new TreeNode(5);
		tree.root.left.right.left = new TreeNode(6);
		tree.root.left.right.left.left = new TreeNode(9);
		tree.root.left.right.right = new TreeNode(8);
		tree.root.left.right.right.left = new TreeNode(3);
		tree.root.left.left = new TreeNode(3);
		tree.root.right = new TreeNode(2);
		tree.root.right.right = new TreeNode(12);
		tree.root.right.right.right = new TreeNode(8);
		tree.root.right.right.left = new TreeNode(5);
		tree.root.right.right.left.right = new TreeNode(15);
		// Test case
		// [4 2 12 8] gcd is 2
		tree.pathGCD();
	}
}

input

 Result : 2
import Foundation;
/*
  Swift 4 program
  Find maximum GCD value from root to leaf in a binary tree
*/
// Binary Tree node
class TreeNode
{
	var data: Int;
	var left: TreeNode? ;
	var right: TreeNode? ;
	init(_ data: Int)
	{
		// Set node value
		self.data = data;
		self.left = nil;
		self.right = nil;
	}
}
class BinaryTree
{
	var root: TreeNode? ;
	var result: Int;
	init()
	{
		self.root = nil;
		self.result = 0;
	}
	// Finding gcd of two numbers using recursion
	func findGCD(_ a: Int, _ b: Int) -> Int
	{
		if (b == 0)
		{
			return a;
		}
		return self.findGCD(b, a % b);
	}
	// Find all path and detecting maximum gcd of path using recursion
	func maxGCD(_ node: TreeNode? , _ path : inout[Int])
	{
		if (node == nil)
		{
			return;
		}
		// Add path element
		path.append(node!.data);
		if (node!.left == nil && node!.right == nil)
		{
			var i = 1;
			// First node of path
			var auxiliary = path[0];
			while (i < path.count)
			{
				auxiliary = self.findGCD(auxiliary, path[i]);
				i += 1;
			}
			if (auxiliary > self.result)
			{
				// New largest gcd of current path
				self.result = auxiliary;
			}
		}
		else
		{
			self.maxGCD(node!.left, &path);
			self.maxGCD(node!.right, &path);
		}
		// Remove last node in path
		path.removeLast();
	}
	// Handles the request of finding maximum gcd in tree path
	func pathGCD()
	{
		if (self.root == nil)
		{
			// Empty Tree
			return;
		}
		else
		{
			// This is use to collect sort path
			var path = [Int]();
			// Reset the resultant gcd
			self.result = Int.min;
			// Find max gcd in binary tree path
			self.maxGCD(self.root, &path);
			// Display calculated result
			print(" Result : ", self.result);
		}
	}
}
func main()
{
	// Create new binary tree
	let tree = BinaryTree();
	/*
	         4                            
	       /   \    
	      20    2    
	     / \     \               
	    3   5     12
	       / \    / \
	      6   8  5   8
	     /   /    \
	    9   3     15 
	-----------------
	Constructing binary tree    
	*/
	tree.root = TreeNode(4);
	tree.root!.left = TreeNode(20);
	tree.root!.left!.right = TreeNode(5);
	tree.root!.left!.right!.left = TreeNode(6);
	tree.root!.left!.right!.left!.left = TreeNode(9);
	tree.root!.left!.right!.right = TreeNode(8);
	tree.root!.left!.right!.right!.left = TreeNode(3);
	tree.root!.left!.left = TreeNode(3);
	tree.root!.right = TreeNode(2);
	tree.root!.right!.right = TreeNode(12);
	tree.root!.right!.right!.right = TreeNode(8);
	tree.root!.right!.right!.left = TreeNode(5);
	tree.root!.right!.right!.left!.right = TreeNode(15);
	// Test case
	// [4 2 12 8] gcd is 2
	tree.pathGCD();
}
main();

input

 Result :  2
/*
  Kotlin program
  Find maximum GCD value from root to leaf in a binary tree
*/
// 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 BinaryTree
{
	var root: TreeNode ? ;
	var result: Int;
	constructor()
	{
		this.root = null;
		this.result = 0;
	}
	// Finding gcd of two numbers using recursion
	fun findGCD(a: Int, b: Int): Int
	{
		if (b == 0)
		{
			return a;
		}
		return this.findGCD(b, a % b);
	}
	// Find all path and detecting maximum gcd of path using recursion
	fun maxGCD(node: TreeNode ? , path : MutableList <Int>  ): Unit
	{
		if (node == null)
		{
			return;
		}
		// Add path element
		path.add(node.data);
		if (node.left == null && node.right == null)
		{
			var i: Int = 1;
			// First node of path
			var auxiliary: Int = path[0];
			while (i < path.size)
			{
				auxiliary = this.findGCD(auxiliary, path[i]);
				i += 1;
			}
			if (auxiliary > this.result)
			{
				// New largest gcd of current path
				this.result = auxiliary;
			}
		}
		else
		{
			this.maxGCD(node.left, path);
			this.maxGCD(node.right, path);
		}
		// Remove last node in path
		path.removeAt(path.size - 1);
	}
	// Handles the request of finding maximum gcd in tree path
	fun pathGCD(): Unit
	{
		if (this.root == null)
		{
			// Empty Tree
			return;
		}
		else
		{
			// This is use to collect sort path
			val path: MutableList < Int > = mutableListOf < Int > ();
			// Reset the resultant gcd
			this.result = Int.MIN_VALUE;
			// Find max gcd in binary tree path
			this.maxGCD(this.root, path);
			// Display calculated result
			println(" Result : " + this.result);
		}
	}
}
fun main(args: Array < String > ): Unit
{
	// Create new binary tree
	val tree: BinaryTree = BinaryTree();
	/*
	         4                            
	       /   \    
	      20    2    
	     / \     \               
	    3   5     12
	       / \    / \
	      6   8  5   8
	     /   /    \
	    9   3     15 
	-----------------
	Constructing binary tree    
	*/
	tree.root = TreeNode(4);
	tree.root?.left = TreeNode(20);
	tree.root?.left?.right = TreeNode(5);
	tree.root?.left?.right?.left = TreeNode(6);
	tree.root?.left?.right?.left?.left = TreeNode(9);
	tree.root?.left?.right?.right = TreeNode(8);
	tree.root?.left?.right?.right?.left = TreeNode(3);
	tree.root?.left?.left = TreeNode(3);
	tree.root?.right = TreeNode(2);
	tree.root?.right?.right = TreeNode(12);
	tree.root?.right?.right?.right = TreeNode(8);
	tree.root?.right?.right?.left = TreeNode(5);
	tree.root?.right?.right?.left?.right = TreeNode(15);
	// Test case
	// [4 2 12 8] gcd is 2
	tree.pathGCD();
}

input

 Result : 2
Last updated on by Kalkicode




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