Find Maximum GCD Value from Root to Leaf in a Binary Tree

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;
}

You can also try this code with Online C++ Compiler

Run Code

Output

5

You can also try this code with Online C++ Compiler

Run Code

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

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 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 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 pre-order 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 Coding Ninjas Studio.

Happy Coding!