Check whether given tree is divisible tree or not


  • 3
    U

    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

  • 0

    I think your example is a valid divisible tree right? You should mention that in the description.


  • 0
    U

    Yes. It is valid divisible tree.


  • 0

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

  • 0
    U

    This is valid only for child nodes and not sub tree as whole. e.g. [4, 3, 8, 16, 15, NULL, NULL] in level order is not divisible. This program will mark it as divisible only.


  • 0

    Aha, I see what you mean now, basically to be a divisible tree, every single node in the left sub tree should be indivisible by the root and every single node in the right sub tree should be divisible by the root.


  • 0

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

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.