### calmhandtitan's blog

By calmhandtitan, history, 4 years ago,

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?

• -12

 » 4 years ago, # | ← Rev. 2 →   0 We can do an algorithm with O(n) pre-calculation and O(log(n)) query: in each node, in addition to the value of the node, we also hold the sum of the subtree of the node. Then, in order to find the different node, we do a search like this: search(node n1, node n2): -- n1 is the node from the first bst, n2 from the second one -- if n1.value != n2.value then return pair(n1, n2) else if exists(n1.left_child) and (n1.left_child.sum != n2.left_child.sum) then return search(n1.left_child, n2.left_child) else return search(n1.right_child, n2.right_child) This is O(depth of result node), which is equivalent with O(log(n))
•  » » 3 years ago, # ^ |   0 Shouldn't O(depth of result node) be upper bounded by O(n). Think of a path like BST, values inserted in increasing order, and last nodes mismatch.
•  » » » 3 years ago, # ^ |   0 I had initially assumed that the question refers to balanced binary search trees (in which case, "depth of result node" <= log(n)). If we're talking about unbalanced binary search trees, then the problem's worst case seems to be O(n), as you said.
•  » » » » 3 years ago, # ^ |   0 Hi taminov, Thank you. As it seems to me, the sum part is calculated using the O(n) pre-calculation. Then, overall time complexity is still O(N). Did I get it right?
 » 4 years ago, # |   0 If we aren't allowed to hold any additional data in each node, I think it is impossible in the worst case. If, for instance, we are at a node, and both children nodes have the same value, there is no way to decide in which child the result is (once again, if we aren't allowed to hold any additional data). In this case, the result node might be in the last node in which we look, which would lead to an O(n) worst case complexity.