0

Okay, so the problem I'm trying to solve is to create a recursive linear-time algorithm to verify a BT at every node. So far, here is my code;

public class BinaryTree {
    Node root;

    private Node addR(Node c, int x, Node parent) {
        if (c == null) {
            c = new Node(x);
            c.parent = parent;
            return c;
        }
        if (x < c.value) {
            parent = c;
            c.left = addR(c.left, x, c);
        }
        else if (x > c.value) {
            parent = c;
            c.right = addR(c.right, x, c);
        }
        else {
            return c;
        }
        return c;
    }
    
    public void add(Node parent, int x) {
        root = addR(root, x, parent);
    }
    
    static int max(Node n) {
        if (n == null) {
            return Integer.MIN_VALUE;
        }
        int value = n.value;
        int leftMax = max(n.left);
        int rightMax = max(n.right);
        return Math.max(value, Math.max(leftMax, rightMax));
    }
        
    static int min(Node n) {
        if (n == null) {
            return Integer.MAX_VALUE;
        }
        int value = n.value;
        int leftMax = min(n.left);
        int rightMax = min(n.right);
        
        return Math.min(value,  Math.min(leftMax, rightMax));
    }
    
    static int verifyBST(Node n) {
        if (n.left != null && max(n.left) > n.value) {
            return 0;
        }
        
        if (n.right != null && min(n.right) < n.value) {
            return 0;
        }
        if (verifyBST(n.left) != 1 || verifyBST(n.right) != 1) {
             return 0;
        }
        return 1;
     }
    
    static void verifyBSTout(int x) {
        if (x == 1) {
            System.out.println ("Confirmed Binary Tree.");
        }
        else {
            System.out.println ("Not a Binary Tree.");
        }
    }
}

And my main;

public class Main {
    public static void main(String[] args) {
        BinaryTree test = new BinaryTree();
        test.add(test.root, 7);
        test.add(test.root, 5);
        test.add(test.root, 6);
        test.add(test.root, 9);
        test.add(test.root, 3);
        test.add(test.root, 8);
        test.verifyBSTout(BinaryTree.verifyBST(test.root));
        
    }
}

I checked to make sure that there was a value for test.root.left.value, but yet when it arrives at the the actual test, it says that n is null and throws a NullPointException. I'm a bit confused since, firstly, I'm passing it the test I just populated, and secondly, the verifyBST method should only use that line if n != null, so I'm not sure why it would crash there due to n != null.

Anybody have any insights as to where my mistake is? Thanks in advance.

Dash Harber
  • 11
  • 3
  • 2
    Given that I didn't check, nor tried to understand the correctness of what you are doing, the `NullPointerException` might be coming from `verifyBST`. If you pass a single node with no leaves to that method, then `n.left` and `n.right` are `null`, correct? So the first condition `if (n.left != null ...)` is skipped, the second condition is also skipped, and then `verifyBST(n.left)` is called again but with a `null` value. Which throws in the first condition since it is calling `n.left` on a null reference. So, check for `null` before calling `verifyBST` or return 1 when `n` is `null` – Turkhan Badalov Apr 16 '23 at 04:34
  • make the first line of `verifyBST()` this: `if (n == null) { return 0; }` (or `return1;` - whatever is appropriate; I can't tell what you're trying to do). An aside: the method name `verifyBST` suggests it should return `boolean`, not `int`. Java ain't C, so `1` and `0` have nothing to do with `true` and `false`. – Bohemian Apr 16 '23 at 05:23
  • 1
    You never check whether `n` is null. – tgdavies Apr 16 '23 at 05:33

1 Answers1

1

Your verifyBST method is calling verifyBST(n.left) when n.left is null - this leads to an NPE. If you change it as follows then the NPE doesn't occur:

static int verifyBST(Node n) {
    if (n.left != null && max(n.left) > n.value && verifyBST(n.left) != 1) {
        return 0;
    }

    if (n.right != null && min(n.right) < n.value && verifyBST(n.right) != 1) {
        return 0;
    }

    return 1;
}
jon hanson
  • 8,722
  • 2
  • 37
  • 61