AlgoVerse

Copying and comparing trees

Two short recursive algorithms: copy a binary tree node by node, and check whether two trees have the same shape and the same keys; both O(n).

A binary tree is copied with a preorder traversal: make a new node with the same key, then copy the left and right subtrees recursively and attach them. Each node is copied once: O(n).

Read the full explanation ↓
Input:
A 1×6 · B 1×6PDF export

A and B are the same keys in two insertion orders that give the same tree; a is copied, and a and b are equal.

  1. class Node:
  2. def __init__(self, key):
  3. self.key = key
  4. self.left = None
  5. self.right = None
  8. def copy_and_compare(A, B):
  9. a = build(A[0])
  10. b = build(B[0])
  11. c = copy(a)
  12. same = equal(a, b)
  13. return same
  16. def copy(node):
  17. if node is None:
  18. return None
  19. t = Node(node.key)
  20. t.left = copy(node.left)
  21. t.right = copy(node.right)
  22. return t
  25. def equal(x, y):
  26. if x is None and y is None:
  27. return True
  28. if x is None or y is None:
  29. return False
  30. if x.key != y.key:
  31. return False
  32. match = x.key
  33. return equal(x.left, y.left) and equal(x.right, y.right)
  36. def build(keys):
  37. # A binary search tree from the keys in this insertion order.
  38. root = None
  39. for k in keys:
  40. node = Node(k)
  41. if root is None:
  42. root = node
  43. continue
  44. p = root
  45. while True:
  46. if k < p.key:
  47. if p.left is None:
  48. p.left = node
  49. break
  50. p = p.left
  51. else:
  52. if p.right is None:
  53. p.right = node
  54. break
  55. p = p.right
  56. return root

Invariant: EQUAL(x, y) is true exactly when the subtrees at x and y have the same shape and the same keys.

Start

a

∅

b

∅

c

∅

same—

Recursion tree

Filled orange = running call · Orange outline = still on the stack · Grey = finished

Local variables

Orange = changed in this step

A list

[8, 4, 12, 2, 6, 10]

B list

[8, 12, 4, 10, 6, 2]

Call stack

  1. copy_and_compare()line 8
Step 1 of 324
Black = copy_node, same_key · Orange = key stepbuilt: 0/1 · copy_node: 0/6 · copied: 0/1 · same_key: 0/6 · compared: 0/1
    Explanation

    Copying

    A binary tree is copied with a preorder traversal: make a new node with the same key, then copy the left and right subtrees recursively and attach them. Each node is copied once: O(n).

    Equality

    Two trees are equal if both are empty, or their roots have the same key and their left and right subtrees are (recursively) equal. The answer is "no" at the first difference, in shape or in a key.

    A note

    The same keys inserted in different orders can give the same binary search tree or a different one; the presets show both.

    The input

    A and B are the insertion orders of the keys into two binary search trees, a and b.