0

I want to write a function that shows me if a given tree is BinarySearch or not.

This is what I wrote so far:

class Node: 

     def _isBinary(self):
        
        L=[]

        if self.left is not None and self.right is not None:
            if self.left.data>self.data or self.right.data<self.data:
               L.append(1)
            else:
               L+=self.left._isBinary()
               L+=self.right._isBinary()
        else:

            if self.left is not None:
               if self.left.data>self.datat:
                  L.append(1)
               else:
                  self.left._isBinary()

            if self.right is not None:
               if self.right.data<self.data:
                  L.append(1)
               else:
                  self.right._isBinary()

       return L

class tree:
    
    def isBinary(self):
        if self.root is None:
            return
        else:
            return  not 1 in self.root._isBinary(self.root.data)

(obisivuly I just reported the interested part of the code) This code works finely, but gives me the incorrect answer when, for example, a number (bigger than the root) is in the left side of the tree, but is the children of a lower number:

     99
    /  \
   8   888
    \
     100

It should give me False, instead it returns True. What can I do? (if possible, without changing completely my original code?)

Jenny
  • 259
  • 1
  • 2
  • 12
  • 1
    Please update the indentation of your code. Python is very sensitive to indentation, as are python programmers. – quamrana Feb 01 '21 at 17:44

5 Answers5

7

A different approach would be to just do an inorder traversal of the BST then check if it is sorted. Inorder traversal of an BST is sorted.

def inorder(node):
    if node is None:
        return
    yield from inorder(node.left)
    yield node.data
    yield from inorder(node.right)


inorder_traversal = list(inorder(root))
print(all(i<=j for i, j in zip(inorder_traversal, inorder_traversal[1:]))) # check if sorted

You can bring in itertools.tee to gain better performance due to the short circuiting nature of all.

inorder_traversal = inorder(root)
a, b = tee(inorder_traversal) # copy the `inorder_traversal` iterator
next(b) # discard first element
print(all(i<=j for i, j in zip(a,b))) # check if sorted

For more information on how tee works you can refer to this answer Iterate a list as pair (current, next) in Python.

python_user
  • 5,375
  • 2
  • 13
  • 32
  • 1
    Why so verbose =) `if node: yield ...` no return needed. – user2390182 Feb 01 '21 at 17:43
  • Also, the cargo seems to be `.data`, not `.val`. Unlike at leetcode... :P – user2390182 Feb 01 '21 at 17:46
  • 1
    Let's just upvote this answer instead of pointing at cosmetic things. – trincot Feb 01 '21 at 17:48
  • @trincot I have upvoted it. However, while the recursive generator is, of course, very elegant, the memory usage and spurious and repeated iteration of the entire tree should not be overlooked when going for the best algorithm. – user2390182 Feb 01 '21 at 17:51
  • 2
    you could bring in `tee` and `all` would short circuit, not sure how much of a benefit that would be compared to recursion – python_user Feb 01 '21 at 17:52
  • 2
    Short circuiting instead of consuming the iterator completely into a list would indeed be an improvement. – trincot Feb 01 '21 at 17:54
  • this is not short-circuiting the way you think it is. also manually calling `next` on an iterator without catching `StopIteration` exception is bad. – Mulan Feb 01 '21 at 18:38
  • @Thankyou how is this not short circuiting? can you explain? also that `StopIteration ` can easily be avoided by doing `if (next(a), None) is not None` before the `all` wont it? – python_user Feb 02 '21 at 01:07
  • because `list(inorder(root))` traverses the entire tree before `all` can begin. and no, your `if` will not work because `next(a)` throws a `StopIteration` exception before it is evaluated. did you try it for yourself? – Mulan Feb 02 '21 at 01:45
  • 1
    @Thankyou the short circuit was for the solution with `tee` where the iterator was not converted to a list at all, this solution was added before your comment and I had also mentioned it above when I edited it – python_user Feb 02 '21 at 01:46
  • @Thankyou ok that was a typo in my last comment, `if (next(a, None))` it should have been this, where it would return `None` – python_user Feb 02 '21 at 01:48
  • calling `next` with a second argument is also a safe use, yes. – Mulan Feb 02 '21 at 01:56
1

Some approach along the following lines should work:

class Node:
    def is_binary_search(self, lo=None, hi=None):
        if lo is not None and lo > self.data:
            return False
        if hi is not None and hi < self.data:
            return False
        if self.left and not self.left.is_binary_search(lo=lo, hi=self.data):
            return False
        if self.right and not self.right.is_binary_search(lo=self.data, hi=hi):
            return False
        return True

You pass those subtree boundaries that are already known (lo and hi) down the recursive calls.

user2390182
  • 72,016
  • 6
  • 67
  • 89
1

You can traverse your tree in sequential order and check that the values are ascending. Using an iterator will avoid the need to create any lists.

def iter(self):
    if self.left:  yield from self.left.iter()
    yield self
    if self.right: yield from self.right.iter()

from itertools import islice
def isBinary(self):
    return all(a<b for a,b in zip(self.iter(),islice(self.iter(),1,None)))
Alain T.
  • 40,517
  • 4
  • 31
  • 51
  • nice use of `islice` to avoid iterating over the whole tree. i enjoy your answers a lot. – Mulan Feb 01 '21 at 19:18
1

Assuming that a node is defined like that

class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.right = right
        self.left = left

This simple recursive function should be sufficient. Passing two different comparator functions for the left and right subtrees as a callable argument to the inner recursive function. Not the shortest possible solution, but doesn't look like black magic (hopefully).

def is_bst(root):
    def is_bst_recursive(node, in_order):
        if node is None:
            return True
        if not in_order(node.value):
            return False
        if node.left and node.left.value >= node.value:
            return False
        if node.right and node.right.value <= node.value:
            return False
        return (is_bst_recursive(node.left, in_order)
                and is_bst_recursive(node.right, in_order))

    return (is_bst_recursive(root.left, lambda x: x < root.value)
            and is_bst_recursive(root.right, lambda x: x > root.value))
Gavin Greenhorn
  • 33
  • 5
0

We can write is_binary_search which takes an input tree, t, and a compare function which defaults to always True -

def is_binary_search(t, compare = lambda _: True):
  if not t:
    return True
  else:
    return compare(t.data) \
       and is_binary_search(t.left, lambda l: compare(l) and l < t.data) \
       and is_binary_search(t.right, lambda r: compare(r) and r > t.data)

We create two trees to test our function -

  • t1, an invalid binary search tree, provided in your example question
  • t2, a valid binary search tree
class node:
  def __init__(self, data, left = None, right = None):
    self.data = data
    self.left = left
    self.right = right

t1 = \
  node(99, node(8, None, node(100)), node(888))

#    99
#   /  \
#  8   888
#   \
#    100


t2 = \
  node(99, node(8, None, node(10)), node(888))

#    99
#   /  \
#  8   888
#   \
#    10

print(is_binary_search(t1)) # False
print(is_binary_search(t2)) # True

We should also test cases like an empty tree, None, and a tree of just a single node, each of which are valid binary search trees -

print(is_binary_search(None)) # True
print(is_binary_search(node(123))) # True
Mulan
  • 129,518
  • 31
  • 228
  • 259