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


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