CODEWITHSUNDEEP
javarecursiongraphtree
Jay S
Jay S

Reputation: 3

Checking if binary tree is a BST

I am confused by the following algorithm:

public static boolean checkBST(TreeNode n) {
    if (n == null) {
        return true;
    }

    // Check / recurse left
    if (!checkBST(n.left)) {
        return false;
    }

    // Check current
    if (last_printed != null && n.data <= last_printed) {
        return false;
    }
    last_printed = n.data;

    // Check / recurse right
    if (!checkBST(n.right)) {
        return false;
    }
    return true;
}

I understand the in-order traversal, and understand comparing the left child of the current node to make sure it's <= to the parent in the line with n.data <= last_printed, but where in this recursion do we check whether the right child is greater than the parent?

Upvotes: 0

Views: 78

Answers (2)

John Bollinger
John Bollinger

Reputation: 180113

The right child is checked in the same way and place as the left child.

The algorithm works as if by printing the value of each node via an in-order traversal, and then checking whether the resulting list is in order. Instead of actually printing, however, it maintains in instance variable last_printed the value that would have been most recently printed at that point in the traversal. Regardless of the progression through the traversal and the path to the current node, the test marked // Check current performs the correct test for whether the current node is traversed in an order consistent with the tree being a BST.

The key thing to note is perhaps that last_printed is updated at the point were the current node is traversed, between traversing the left subtree and the right subtree.

Upvotes: 1

Spilker22
Spilker22

Reputation: 319

What do your left and right methods do? Are you just trying to verify that you have a binary search tree?

Upvotes: 0

Related Questions