Hello everyone!
Can you say please, do we have a solution to find LCA of two nodes in binary tree visiting every tree node only once?
Nodes only have left, right references without parent.
Requrementes: O(n) time complexity, constant memory space, every tree node is visiting only once.
C, C++, Java, or pseudocode is enough to implement this algo if it exists.
Can anyone show solution of this problem?

| Сообщение посчитали полезным:

No. It's too difficult

However go to --> Link <--



| Сообщение посчитали полезным:

TheNozza
are you passing the google & | MS screening?

| Сообщение посчитали полезным:

<<are you passing the google & | MS screening?
Not yet. I have found compact solution of this problem. And I want to check if this solution already exists.

In the book "Cracking the Coding Interview, 4 Edition" for task 4.6 there are 3 solutions. You can see there, that algorithm traverses each node of tree more than once.

I can't find in internet how to solve problem visiting every tree node only once.
Here http://blog.gainlo.co/index.php/2016/07/06/lowest-common-ancestor/ you can see mention, that it is possible: "Since we traverse all nodes at most once without external space, both time and space complexity is O(N).", but without code.

| Сообщение посчитали полезным:

note the LCA is a node which has values you looking for in different branches. Use recursion call to find such node.

-----
старый пень

| Сообщение посчитали полезным:

can you show a code? for example post url to code in internet, which solves this problem. My solution has ~ ten strings of code, and of course it uses recursion.

| Сообщение посчитали полезным:

If you have solution what else do you want?

-----
старый пень

| Сообщение посчитали полезным: