713149. Parent of Max GCD Siblings in a Binary Tree
Easy
Parent of Max GCD Siblings in a Binary Tree
Slug: find-the-node-with-maximum-gcd-of-the-siblings-of-a-binary-tree
Difficulty: Easy
Topic Tags: Tree, Data Structures
Company Tags: Samsung
Summary
Find the node with maximum GCD (Greatest Common Divisor) of its siblings in a binary tree. The problem involves traversing and manipulating nodes in a tree data structure.
Detailed Explanation
The problem can be solved by performing an in-order traversal of the binary tree, calculating the GCD for each node's siblings, and keeping track of the maximum GCD found. Here's a step-by-step breakdown:
- Perform an in-order traversal of the binary tree to visit nodes in ascending order.
- For each node, calculate the GCD of its left and right child (if they exist).
- Keep track of the maximum GCD found so far.
- When the traversal is complete, return the node with the maximum GCD.
The time complexity for this solution is O(n), where n is the number of nodes in the tree, since we visit each node once. The space complexity is O(1) as we only use a constant amount of space to store the maximum GCD and other variables.
Optimized Solutions
Java
class Node {
int val;
Node left, right;
public Node(int v) {
val = v;
left = right = null;
}
}
public class Main {
public static void main(String[] args) {
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
int maxGCD = findMaxGCD(root);
System.out.println("Node with maximum GCD: " + maxGCD);
}
public static int findMaxGCD(Node node) {
if (node == null)
return 0;
int leftGCD = (node.left != null) ? getGCD(node.val, node.left.val) : 0;
int rightGCD = (node.right != null) ? getGCD(node.val, node.right.val) : 0;
if (leftGCD > rightGCD)
return leftGCD;
else
return rightGCD;
}
public static int getGCD(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
}