Skip to main content

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
    add node.data to path
    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;
        }
        // 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

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.

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