# Find maximum GCD value in binary tree path

The problem revolves around finding the maximum Greatest Common Divisor (GCD) value along a path from the root to a leaf node in a binary tree. It entails traversing different paths, calculating the GCD of the numbers along each path, and then identifying the maximum GCD value among all paths.

## Problem Statement

Given a binary tree, the goal is to determine the maximum GCD value along any path from the root to a leaf node. For each path, the program calculates the GCD of all the values along that path and keeps track of the maximum GCD encountered.

## Example

Consider the binary tree described in the code:

``````         4
/   \
20    2
/ \     \
3   5     12
/ \    / \
6   8  5   8
/   /    \
9   3     15

path [4 2 12 8] gcd is : 2
``````

For this tree, the maximum GCD value along a path is 2, which corresponds to the path `[4, 2, 12, 8]`.

## Idea to Solve

The problem can be solved using a recursive approach. We traverse the binary tree and maintain a path as we move from the root to the leaf nodes. Along each path, we calculate the GCD of the values encountered and update the maximum GCD value if the calculated GCD is larger. This process is repeated for all paths, and the maximum GCD value is stored.

## Pseudocode

``````function findGCD(a, b):
if b is 0:
return a
return findGCD(b, a % b)

function maxGCD(node, path):
if node is null:
return
if node is leaf node:
set auxiliary to first element of path
for i from 1 to size of path - 1:
auxiliary = findGCD(auxiliary, path[i])
if auxiliary > result:
set result to auxiliary
else:
maxGCD(node.left, path)
maxGCD(node.right, path)
remove last element from path

function pathGCD():
if root is null:
return
create empty path list
set result to Integer.MIN_VALUE
call maxGCD(root, path)
print "Result:", result

main:
create binary tree
construct tree as shown
call pathGCD()``````

## Algorithm Explanation

1. The `findGCD` function calculates the GCD of two numbers using the Euclidean algorithm.
2. The `maxGCD` function recursively traverses the binary tree and maintains the path as it moves from the root to the leaf nodes. Along each path, it calculates the GCD of the values and updates the maximum GCD value encountered.
3. The `pathGCD` function initializes an empty path list and the `result` variable to store the maximum GCD value. It calls `maxGCD` and prints the final result.
4. In the `main` function, a binary tree is constructed, and `pathGCD` is called.

## Program Solution

``````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;
}
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;
}
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;
}
if (node.left == null && node.right == null)
{
int i = 1;
// First node of path
int auxiliary = path;
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;
}
\$path[] = \$node->data;
if (\$node->left == NULL && \$node->right == NULL)
{
\$i = 1;
// First node of path
\$auxiliary = \$path;
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;
}
path.push(node.data);
if (node.left == null && node.right == null)
{
var i = 1;
// First node of path
var auxiliary = path;
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

path.append(node.data)
if (node.left == None and node.right == None) :
i = 1
#  First node of path
auxiliary = path
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_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_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

path.push(node.data)
if (node.left == nil && node.right == nil)
i = 1
#  First node of path
auxiliary = path
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;
}
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;
}
path.append(node!.data);
if (node!.left == nil && node!.right == nil)
{
var i = 1;
// First node of path
var auxiliary = path;
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;
}
if (node.left == null && node.right == null)
{
var i: Int = 1;
// First node of path
var auxiliary: Int = path;
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``

## Time Complexity

The time complexity of the solution mainly depends on the number of nodes in the binary tree, as each node is visited once. In the worst case, we would traverse all paths from the root to the leaf nodes, resulting in a time complexity of O(n), where n is the number of nodes in the binary tree.

## 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.