Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

Binary search trees

Revision en1, by calmhandtitan, 2016-07-31 09:14:13

Given two binary search trees with identical structure, same node value but just one node with different values, how can we determine this node (by determining the node I mean the path from root to this node).

An obvious solution is to do traversal for both the trees and keep track of the path. But this would take O(n).

My question is can we do better than O(n) for this problem?

Tags binary search tree

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English calmhandtitan 2016-07-31 09:14:13 408 Initial revision (published)