Python Binary Search Tree Implementation
docstrings

Docstrings matter. Delete the cryptic #BST comment and spell it out in a PEP8 class docstring:

class Node:
"""Implements a Binary Search Tree."""


Either search or __init__ needs a docstring that mentions the equality case (I'm looking at elif root.val &lt; k:, as opposed to &lt;= k).

correctness

I can't imagine successor is correct. You didn't offer any unit tests like this, but I'm thinking of passing in a node with no right subtree, a node having the same value as root. Then we return None ?? This comes back to the &lt;= k detail I mentioned above. Anyway, predecessor is nicely parallel, simple is good. And insert is beautiful and concise.

public API design

For some methods, rather than passing in root, it would be more natural to be working with an instance of your BST class, with self.root implicitly available. 

style

As a trivial style detail, in parent you might use parentheses a level deeper to remove the backslash.

I didn't run flake8 myself, but overall it looks good. I have a weak preference for if node.left: instead of if node.left is not None:.

tests

I'm looking at this:

class BSTTest(unittest.TestCase):
    def test_recursive_search(self):
        root  = build_bst()
        actual = search(root, 35).val
        expected = 35
        self.assertEqual(expected, actual)


I would much rather see the method expressed concisely:

    def test_recursive_search(self):
        root  = build_bst()
        self.assertEqual(35, search(root, 35).val)


It might even come out as:

    def test_recursive_search(self):
        self.assertEqual(35, search(self.root, 35).val)


where build_bst() is invoked by a setup method.

There are other tests, e.g. test_insert_on_empty_tree, where of course hanging on to an actual temp variable is the natural way to express it.

I am very glad to see these tests. They appear to give reasonable code coverage.

Another example tree that stores multiple copies of a given value (e.g. 30) would be of interest.

summary

Overall it looks good! Ship it.