# Find maximum GCD value from root to leaf in a Binary Tree

## 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 non-zero integers is the largest non-zero positive integer, which divides both the 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

**O(n^2)**, where n = total number of nodes in the tree

**Reason**: We are traversing the tree in a pre-order 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

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

## 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 root to leaf path in a binary tree?**

A path from the root of a tree to any leaf node is called a root to leaf path.

**What is the GCD of two numbers?**

The GCD of two numbers a,b is the largest positive number which divides both a and b.

## Key Takeaways

In this article, we’ve discussed a problem related to the binary tree. To solve it, we traversed the whole tree in the __pre-order traversal__**.** You can look for more problems based on the binary tree. Some of these are the __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__, and __height of the binary tree__. These questions are asked during various __coding contests__ as well as __placements tests.__

To practice more such problems, __Codestudio__ is a one-stop destination. This platform will help you acquire effective coding techniques and overview student interview experience in various product-based companies.

Happy Coding!

Comments

## No comments yet

## Be the first to share what you think