Problem Solutions

Question 1

Validate BST:

“Implement a function to check if a binary tree is a binary search tree”

Answer 1

1. In-order traversals of BST are always increasing. Leverage this property. (cannot handle duplicate vals)
2. Min/Max solution. Leverage definition of binary tree. Pass min/max values and update the bounds as recursion (or iteration) continues

Question 2

Successor:

“Write an algorithm to find the ‘next’ node (i.e. in-order successor) of a given binary search tree. You may assume that each node has a link to its parent.

Answer 2

1. If node has node.right, then go left as possible down node.right.
2. If node does not have node.right, traverse up the tree until you find a node x where x.left = node. x is the successor. If we reach the root and no such x exists, return None.

Note: this is effectively a database cursor.