Introduction
A binary tree is a tree data structure in which each node has two children, referred to as the left child and the right child. The end nodes which don’t have any children are called leaf nodes. The root node is the node at the top.
GCD of two nonzero integers is the largest nonzero positive integer, which divides both integers. If the numbers are a,b and the GCD is c, then we write gcd(a,b) = c.
Let’s see how to find the maximum GCD value from root to leaf in a binary tree.
Problem Statement
Given a binary tree, find the maximum GCD value among all the GCD values of the paths from the root to leaf nodes.
For example,
Input:
Output: 5
Explanation: In the above tree, the paths are:
[60>28>8] > gcd(60,28,8) = 2
[60>20>10>5] > gcd(60,20,10,5) = 5
[60>20>18>3] > gcd(60,20,18,3) = 1
Thus the maximum GCD is 5.
Solution Approach
Since we need the GCDs of the paths, we will keep traversing the tree in preorder traversal until each time we get to a leaf node and then find the gcd of that path. If the gcd is greater than the existing answer gcd, we will update the answer gcd. Initially, we keep the answer gcd as INT_MIN. Print the answer gcd in the end.
Steps are:
 Construct a binary tree
 Initialize a variable ans to INT_MIN as it will contain the maximum GCD of all paths.

Call the function “func,” which finds the maximum GCD value from root to leaf in a Binary Tree. In the function “func”:
 If the root is null, terminate the process and return.
 Otherwise, push the data of the current node in the path vector.
 If the current node is a leaf node, we have found a complete path, and now we need to calculate the gcd of this path.
 For finding the GCD of the path, initialize a variable curr_gcd to the first element of the path vector. Calculate the gcd of the curre_gcd variable with each element of the path vector. This will give the GCD of the current path.
 If the GCD is greater than the current answer, update the answer.
 Print the value of ans.
C++ implementation
#include<bits/stdc++.h>
using namespace std;
template <typename T>
class BinaryTreeNode{ // Class for BinaryTreeNode
public:
T data; // Data of the node
BinaryTreeNode* left; // Left of the node
BinaryTreeNode* right; // Right of the node
BinaryTreeNode(T data){ // Constructor for assigning the data to the current node
this>data=data;
left=NULL; // Initialize the left and right pointer to NULL
right=NULL;
}
};
// Function to find the maximum GCD value from root to leaf in a Binary Tree
void func(BinaryTreeNode<int>* root,vector<int>&path, int &ans){
// If root is null, return
if (root==NULL)
return;
path.push_back(root>data); // Push the current node into the path vector
//If the current node is a leaf node, we have found a complete path and
// now we need to calculate the gcd of this path.
if(root>left==NULL && root>right==NULL){
int curr_gcd = path[0];
// Find the gcd of the current path
for(auto x:path){
curr_gcd = __gcd(curr_gcd,x);
}
// If the gcd is greater than the answer, update the answer
if(curr_gcd>ans){
ans = curr_gcd;
}
}
else{
// Else, go keep traversing the tree in preorder traversal
func(root>left,path,ans);
func(root>right,path,ans);
}
// Pop back the current node if the subtree of the current node is
// totally visited
path.pop_back();
}
int main()
{
// Construct a Binary Tree
BinaryTreeNode<int> *root = NULL;
root = new BinaryTreeNode<int>(60);
root>left = new BinaryTreeNode<int>(28);
root>right = new BinaryTreeNode<int>(20);
root>left>left = new BinaryTreeNode<int>(8);
root>right>left = new BinaryTreeNode<int>(10);
root>right>right = new BinaryTreeNode<int>(18);
root>right>left>left = new BinaryTreeNode<int>(5);
root>right>right>right = new BinaryTreeNode<int>(3);
vector<int>path;
// Call the function which returns the root of the smallest subtree
// containing the deepest nodes
int ans = INT_MIN;
func(root,path,ans);
// Print the answer
cout<<ans<<endl;
}
Output
5
Complexities
Time complexity
The Time Complexity is O(n^2), where n = total number of nodes in the tree
Reason: We are traversing the tree in a preorder manner which takes O(n) time. And calculating the GCD each time we reach a leaf node takes another O(n) time. Thus, the total complexity will be O(n^2).
Space complexity
The Space Complexity is O(n), where n = total number of nodes in the tree
Reason: We store each path in a vector. Therefore, the space complexity will be O(n) in the worst case.
Check out this problem  Root To Leaf Path
Frequently Asked Questions
What is a binary tree?
A binary tree is a tree data structure in which each node has at most two children, referred to as the left child and the right child.
What is a binary tree used for?
In computing, binary trees are mainly used for searching and sorting as they provide a means to store data hierarchically.
What is a roottoleaf path in a binary tree?
A path from the root of a tree to any leaf node is called a roottoleaf path.
What is the GCD of two numbers?
The GCD of two numbers a,b is the largest positive number that divides both a and b.
Conclusion
In this article, we’ve discussed a problem related to the binary tree. To solve it, we traversed the whole tree in the preorder traversal. You can look for more problems based on the binary tree.
Recommended Problems:
 Largest number in a binary tree
 Triplets in a binary tree
 Maximum depth of a binary tree
 LCA of a binary tree
 Minimum depth in a binary tree
 Height of the binary tree
 Deepest Left
Recommended Reading:
 Sum of Heights of All Individual Nodes in Binary Tree
 Maximum Average of Subtree Values in a Given Binary Tree
 Find K Smallest Leaf Nodes From the Given Binary Tree
Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on CodeStudio.
Happy Coding!