Left child of root should be indivisible by root and right child should be divisible. This property should be valid not only for children but all sub-trees.
e.g. is a valid divisible tree.
4
/ \
5 8
/ \ / \
7 15 12 16
Here is my postorder solution, not sure if it covers all the cases.
public boolean isDivisibleTree(TreeNode root) {
if (root == null) {
return true;
}
boolean left = isDivisibleTree(root.left);
boolean right = isDivisibleTree(root.right);
if (!left || !right) {
return false;
}
if (root.left != null && (root.val == 0 || root.left.val % root.val == 0)) {
return false;
}
if (root.right != null && (root.val == 0 || root.right.val % root.val != 0)) {
return false;
}
return true;
}
Updated solution based on the clarification, a divisible tree is a binary tree in which every single node in the left sub trees should be indivisible by the root and every single node in the right sub trees should be divisible by the root, and this rule recursively applies to all the nodes.
One technique I can think of is using nested preorder traversal, there maybe a better solution though.
public class Solution {
public boolean isDivisibleTree(TreeNode root) {
if (root == null) {
return true;
}
if (!helper(root.left, root.val, false) || !helper(root.right, root.val, true)) {
return false;
}
return isDivisibleTree(root.left) && isDivisibleTree(root.right);
}
// helper function checks whether all the nodes in tree root can be
// or cannot be divisible by the root.
private boolean helper(TreeNode root, int value, boolean divisible) {
if (root == null) {
return true;
}
if (value == 0) {
return false;
}
if ((divisible && root.val % value != 0) || (!divisible && root.val % value == 0)) {
return false;
}
return helper(root.left, value, divisible) && helper(root.right, value, divisible);
}
}