Recursion Under if-loop

Revision en2, by Suraj_IOI, 2018-09-19 10:48:52

This program checks whether a Binary tree is a BST or not, can someone explain me the working of recursive return statement in the function isBSTUtil class Node { int data; Node left, right;

public Node(int item) 
{ 
    data = item; 
    left = right = null; 
}

}

public class BinaryTree { Node root; boolean isBST() { return isBSTUtil(root, Integer.MIN_VALUE, Integer.MAX_VALUE); } boolean isBSTUtil(Node node, int min, int max) { if (node == null) return true;

if (node.data < min || node.data > max) 
        return false; 

    return (isBSTUtil(node.left, min, node.data-1) && 
            isBSTUtil(node.right, node.data+1, max)); 
} 

public static void main(String args[]) 
{ 
    BinaryTree tree = new BinaryTree(); 
    tree.root = new Node(4); 
    tree.root.left = new Node(2); 
    tree.root.right = new Node(5); 
    tree.root.left.left = new Node(1); 
    tree.root.left.right = new Node(3); 

    if (tree.isBST()) 
        System.out.println("IS BST"); 
    else
        System.out.println("Not a BST"); 
}

}

Tags bst, binary tree, #data structure, #help

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English Suraj_IOI 2018-09-19 10:51:28 328
en4 English Suraj_IOI 2018-09-19 10:50:11 6 Tiny change: '\n{ \n Nod' -> '\n{ \n \n Nod'
en3 English Suraj_IOI 2018-09-19 10:49:39 7
en2 English Suraj_IOI 2018-09-19 10:48:52 2 Tiny change: 'e root; \n\n bool' -> 'e root; \n bool'
en1 English Suraj_IOI 2018-09-19 10:47:17 1314 Initial revision (published)