### 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

By calmhandtitan, history, 5 years ago, ,

From quite a long time I was trying to solve this problem 225D - Snake, but I am stuck on how to create a mask for this snake and how to extract information from the mask for doing further BFS.

I referred to I_love_Tanya_Romanova's solution 4086309 for the same, but was unable to understand the magic behind his mask.

So can someone help me understanding how to create mask for this problem.

Many others have used a hash function to solve this problem. I wonder how?

• 0

By calmhandtitan, history, 5 years ago, ,

Can someone please help tell me why I am getting WA for 131D - Subway or where my code goes wrong.

I get WA at test8 which is a very big test having 3000 nodes for which I am unable to debug.

Here's my submission. 11783845

My intended algorithm is as follows:

1. First find all the vertices in the ring(cycle) using dfs().

2. Then do DFS for each of the vertex in the ring to find the distance of each node from the ring. This is done by dfs2()

This algorithm is the same as mentioned in the editorial

Seeking some help. Thank you. :)