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

calmhandtitan's blog

By calmhandtitan, history, 4 years ago, In English,

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?

 
 
 
 
  • Vote: I like it
  • -12
  • Vote: I do not like it

»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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, # |
  Vote: I like it 0 Vote: I do not like it

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.