Why is this code for Binary Tree failing certain test cases?

Question

I am working on this code challenge:

Problem Description

You are given a family tree with the ages of each person and their children in the form of a binary tree where each parent has at most 2 children. You have to check whether the family tree is valid or not i.e. the age of child nodes should be less than the parent node itself.

Input Format

• First line contains an integer T - Number of test cases.
• First line of each test case contains an integer N - Number of nodes.
• Second line of each test case contains N integers - Age of i^th person.

Next N lines describe the binary tree in the format -

• (node, left child, right child).

Here, node will range from 1 to N i.e. for each person there will be one line. The left child and right child will be either -1 (indicating no child) or another Node number between 1 to N indicating that it is a child.

Output Format

Print "Yes" or “No” depending on whether the given tree is valid or not.

Constraints

• T <= 10
• N <= 10^5
• Age <= 10^6

Sample Input 1

2
4
10 5 9 7
1 2 3
2 -1 -1
3 4 -1
4 -1 -1
3
4 9 3
1 2 3
2 -1 -1
3 -1 -1

Sample Output 1

Yes
No

Note that in the given code stub, you’ll directly be given the TreeNode pointing to the head of the tree as input. You have to return true or false for that tree.

Explanation 1

Instructions to create custom input for a Binary Tree In order to specify a binary tree that can be used as custom input to the problem, you’ll need to follow this convention. (Note that this is after the "Number of test cases" line)

• Line 1: Number of nodes in the Binary Tree (N)
• Line 2: N space separated node values. The position of the Nodes on this line will be used to refer to them in the below lines, starting from 1.
• Line 3 to N+2: Lines specifying the child nodes for each of the N nodes

Format of each line (space separated):

• Parent_node Left_child_node Right_child_node
• Parent_node - Node at this Position on Line 2 is the Node to which we are assigning the Left and Right child here
• Left_child_node - Node at this position on Line 2 is the left child. Specify -1 if there is no Left child.
• Right_child_node - Node at this position on Line 2 is the right child. Specify -1 if there is no Right child.

Example1

Code

The following is my code

import crio.ds.Tree.*;
/*
// Definition of TreeNode
public class TreeNode {
    public long val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode (long x) {
        val = x;
        left = null;
        right = null;
    }
}
*/
public class Solution {
    
    static boolean validFamilyTree(TreeNode root){

        long left_val = -1, right_val = -1;

        if(root == null || (root.left == null && root.right == null)){
            return true;
        }

        else{
            if(root.left != null){
                left_val = root.left.val;
            }
            if(root.right != null){
                right_val = root.right.val;
            }
            if(root.val > left_val && root.val > right_val){
                return true;
            } else{
                return false;
            }
        }
    }
}

My code succeeds for the sample input test case and some edge cases, but failing for a whole lot of other test cases and performance cases.

Why does my code fail those tests?

Answer 1

Your code only looks at the root and its direct children. It never looks at the situation in the sub trees of the tree. For instance, the grandchildren of the root are never inspected, and when they violate the age requirement, your function could still return true.

You'd need to call the function itself on both sub trees below the root. If such a recursive call returns false, you can immediately return false to the caller, as one violation is enough to reject the whole tree.

Not a problem, but the following is an anti pattern:

if (condition)
    return true;
else
    return false;

Instead, you should just do:

return condition;

In fact, in this case the whole logic can be expressed in one boolean expression, which can be the function's return value:

static boolean validFamilyTree(TreeNode root) {
    return root == null ||
        (root.left == null || 
             root.val > root.left.val && validFamilyTree(root.left)
        ) &&
        (root.right == null || 
             root.val > root.right.val && validFamilyTree(root.right)
        );
}