Part of Microsoft
Engaged Employer
LinkedIn Interview Question
How to validate is a binary search tree is legit?
Interview Answer
Anonymous
Jun 9, 2013
1. root node value: upper_limit = none lower_limit = none 2. for every other tree node value: 2.1. if this node is a left child: upper_limit = parent.value lower_limit = parent.lower_limit 2.2. if this node is a right child: upper_limit = parent.upper_limit lower_limit = parent.value 3. traverse the tree using whatever order, return 'invalid' if any node's value violates its upper or lower limt