Disordered Binary Search Trees

March 10, 2017

In a recent exercise we wrote a program to determine if a binary tree was balanced. Today’s exercise is similar:

Write a program to determine if a binary tree satisfies the binary search tree property that all left children are less than their parent and all right children are greater than their parent.

Your task is to write a program to determine if a binary tree is a binary search tree. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Advertisements

Pages: 1 2

3 Responses to “Disordered Binary Search Trees”

  1. Paul said

    @programmingpraxis: If I understand your definition of a BST given in the solution, then the following tree would be a BST:

    ├── 10 (root)
    │ ├── 40
    │ └── 5
    │ ├── 20
    │ └── 1

    The tree at the left (with root value 5 and children 1 and 20) is a BST, but the total tree is not, as in the left tree the value 20 is higher than 10.

    Below an iterative solution in Python. Recursive is not a good idea for this in Python, because it would not work for large trees.

    def is_bst(root):
        Q = [(root, -inf, inf)]
        while Q:
            node, lo, hi = Q.pop()
            if not node:
                continue
            if not lo < node.value < hi:
                return False
            Q += [(node.lft, lo, node.value), (node.rgt, node.value, hi)]
        return True
    
  2. Paul said

    Unfortunately the tree is not printing well (it does in “preview”). The tree is:
    root: 10 with children 5 and 40
    left child of root: 5 with children 1 and 20

  3. Paul said

    ANother try to print the tree

    ├── 10
    │   ├── 40
    │   └── 5
    │       ├── 20
    │       └── 1
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: