We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Loading...
  1. Practice
  2. Tutorials
  3. Cracking the Coding Interview
  4. Trees: Is This a Binary Search Tree?
  5. Discussions

Trees: Is This a Binary Search Tree?

  • sayanarijit + 2 comments

    My code is:

    def isBST(root):
    if root.left and root.left.data >= root.data:
        return False
    if root.left:
        print(root.left.data,"<",root.data)
    if root.right and root.right.data <= root.data:
        return False
    if root.right:
        print(root.right.data,">",root.data)
    return True

def checkBST(root):
    if not isBST(root):
        return False
    if root.left:
        checkBST(root.left)
    if root.right:
        checkBST(root.right)
    return True

    Input:

    2
1 2 4 3 5 6 7

    Output:

    2 < 3
6 > 3
1 < 2
4 > 2
5 < 6
7 > 6
Yes

    Can anyone please where is the problem?

    • kevinpaulboucher + 0 comments
      [deleted]
    • ChrisGBloom + 1 comment

      I know you have probably forgotten about this problem, but I had the same question and found an answer, so hopefully this helps somebody else who comes along:

      The tree in question is:

      ----3

      -2-----6

      1-4---5-7

      in a BST, all nodes and subnodes on the left must be less than the current node, and all nodes and subnodes to the right must be greater than the current node. The reson its not a BST is that 4 is to the left of 3

      • tutu_p + 0 comments

        Thx I was missing this!