Bypass Binary-Tree, how to make it faster?

Question

Python

At the interview, I came across the task of comparing two sequences of numbers stored in two binary trees. I blunted, trying to invent a bypass with a queue right away, after scratching my head and making it, but the interviewer says what can be done in O (n) on unbalanced trees and there is no reason not to believe him.

At first, my recursion went to empty elements too, now there is a condition, but I'm not sure if this is still the best option. I read the chapter from Knuth about trees (Chapter 2.3.1), everything seems to be clear, but after the devastating interview, I now doubt every line. We are talking about a minimalistic bypass, so you can remove itertools due to recopying elements, and catch exceptions yourself.

import itertools

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def tree_walk(node):
    if node.left:
        yield from tree_walk(node.left)
    yield node.value
    if node.right:
        yield from tree_walk(node.right)

def cmp_tree(node1, node2):
    for v1,v2 in itertools.zip_longest(tree_walk(node1), tree_walk(node2)):
        print(v1, v2)
        if v1 != v2:
            return False

    return True

"""
root1:
1
  2
    3

root2:
    3
  2
1

root3:
  2
1   3
      4
"""

root1 = Node(1)
root1.right = Node(2)
root1.right.right = Node(3)

root2 = Node(3)
root2.left = Node(2)
root2.left.left = Node(1)

root3 = Node(2)
root3.left = Node(1)
root3.right = Node(3)
root3.right.right = Node(4)

print(cmp_tree(root1, root2))
print()
print(cmp_tree(root2, root3))

UPD:
As it turned out, the code is already with linear complexity. Marked answer about comparing trees, see comments deeper.

Answer 1

Your problem with the solution is that you are comparing 2 iterations. This is not true for, as you have already been given as an example, these two trees:

1
 \
  2
   \
    3

    3
   /
  2
 /
1

Here both bypasses will return 1,2,3.
You can add any separators in your solution when you move left-right-up. Insert any yeild -1 and other values ​​before going to the left, outputting the element itself, and going to the right.
But there is a better solution, via DFS or BFS: you do the traversal on two trees at the same time. Those. you have a dfs function parameter or there are 2 vertices in the bfs queue at once - one from each tree. You check that they have the same values ​​and that they both have or don't have a left and a right child at the same time. Then you call/put in the queue both the left children and the right children at the same time. If during the traversal the vertices turned out to be different, or somewhere there is a child, but somewhere not, then the trees are not equal.
Very logically implemented in the form of DFS (pseudocode below):

Equals(t1, t2):
   // обработать случай null одного или обоих деревьев.
   return t1.v == t2.v && Equals(t1.left, t2.left) && Equals(t1.right, t2.right)

Everything is extremely logical - 2 trees are equal if they have equal roots, left subtrees and right subtrees.
By the way, your solution, if corrected, will also be in O(n).

Answer 2

1) Python can't drop its tail. Using recursion and PLs that do not know how to tail optimize is a so-so idea. Especially on the abstract tree traversal problem. Especially if they immediately said that the tree is "strongly unbalanced". Therefore, with a slight movement, your decision turns into a pumpkin.

root1 = Node(1)
cur_node = root1
for i in range (0, 1000):
    cur_node.left = Node(i)
    cur_node = cur_node.left

2) these two trees come out the same for you. As graphs - yes, they are the same. symmetrical. Like trees - no, they are different.

root1 = Node(1)
root1.right = Node(2)
root1.right.right = Node(3)

root2 = Node(3)
root2.left = Node(2)
root2.left.left = Node(1)

So first you need to fix, and then think about how to make it faster