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

Shreya Deep
Last Updated: May 13, 2022

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

  1. 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.
     
  2. 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.
     
  3. 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.
     
  4. 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 treetriplets in a binary treemaximum depth of a binary treeLCA of a binary treeminimum depth in a binary tree, and height of the binary treeThese 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!

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think