Yet another interview question:

Implement a function to check if a tree is balanced. For the purposes of this question, a balanced tree is defined to be a tree such that no two leaf nodes differ in distance from the root by more than one.

Frist off, did I understand the question correctly? In other words, we are looking for a subtree in a tree (or rotation of it) that looks like:

     root
    /    \
 leaf_1  leaf_2
  /
leaf1_1

My initial idea was to count the depth of the tree and check if maxDepth - minDepth < 2 (which requires 2 traversal) . But I think I found more efficient solution. The trade-off is that we should keep the ref to the root. I assume n-ary Tree.

import java.util.LinkedList;

public class Trees {
    
    Node threeRoot;
    private boolean isBalanced = true;
    
    Trees(Node threeRoot){
        this.threeRoot = threeRoot;
    }
    
    static class  Node{
        public Node root;
        public LinkedList<Node> children = new LinkedList<>();        
    }
    
     boolean isBalanced(Node node){
       if (threeRoot == null) {
            isBalanced = true;
        }
        if (threeRoot.children == null || threeRoot.children.isEmpty()) {
            isBalanced = true;
        }
        
        isBalancedRed(node);          
        return isBalanced;
    }

     void isBalancedRed(Node node) {
        if (node.children.isEmpty()) {
            if (node.root != null && node.root.children.size() == 1) {
                isBalanced = false;
            }
        }
        for(Node nodeEl : node.children)
        {
            isBalancedRed(nodeEl);
        }
    }
    
    public static void main(String[] args){
        Trees tree = new Trees(new Node());
        Node root = tree.threeRoot;
        Node leaf1 = new Node();
        Node leaf2 = new Node();
        Node leaf11 = new Node();

        root.children.add(leaf1);
        leaf1.root = root;
        root.children.add(leaf2);
        leaf2.root = root;
             
        leaf2.children.add(leaf11);
        leaf11.root = leaf2;
        
        System.out.println(tree.isBalanced(root));           
    }        
}

Is this correct?