Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Solution Approach
3.1.
C++ implementation
3.1.1.
Output
3.2.
Complexities
3.2.1.
Time complexity
3.2.2.
Space complexity
4.
Frequently Asked Questions
4.1.
What is a binary tree?
4.2.
What is a binary tree used for?
4.3.
What is a root-to-leaf path in a binary tree?
4.4.
What is the GCD of two numbers?
5.
Conclusion
Last Updated: Mar 27, 2024

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

Author Shreya Deep
0 upvote
Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

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

Binary Tree

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.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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

Recommended Reading:

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!

Live masterclass