Meta Interview Question

Given two BST, return true if they have same variable, flase if not.

Interview Answer

Anonymous

Feb 28, 2016

Inorder traversals iterates elements in sorted order. simultaneously do inorder traversal on both BSTs, on each iteration advancing bst with smaller head. terminate when a) match is found or b) one or both iterators are exhausted. O(min(m,n)) time, constant space