daily_questions/binaryTreeComparison.py at master · dlefcoe/daily_questions · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
'''


This problem was asked by Google.

Given two non-empty binary trees s and t,
check whether tree t has exactly the same structure and node values with a subtree of s.

A subtree of s is a tree consists of a node in s and all of this node's descendants.
The tree s could also be considered as a subtree of itself.


'''


# A Python class that represents an individual node
# in a Binary Tree
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None


# create roots for 2 different trees
s = Node(1)
t = Node(1)

#create nodes for s
s.left = Node(2)
s.right = Node(3)


s.left.left  = Node(4)
'''4 becomes left child of 2
           1
       /       \
      2          3
    /   \       /  \
   4    None  None  None
  /  \
None None'''

#create nodes for t
t.left = Node(2)
t.right = Node(3)


t.left.left  = Node(3) # testing by setting !=


def compareBinTree(s, t):
    ''' compare two binary trees, s & t

    if they match, return true
    if they do not match, return false

    '''

    # perform comparison
    if s.val == t.val:
        print('roots are the same')
        res = True
    else:
        print('unequal roots')
        res = False

    # check for left nodes
    if s.left and t.left:
        print('s.left and t.left exists')
        if s.left.val == t.left.val: # check if values are equal
            print('left nodes match')
            res = True
            # work on left subtree recursively
            compareBinTree(s.left,t.left)
        else:
            print(f'{s.left.val} is not equal to {t.left.val}')
            res = False
            return res

    if not s.left and not t.left:
        print('s.left and t.left both do not exits')
        res = True

    if (not s.left and t.left) or (s.left and not t.left):
        print('s and t do not match, s = {s.left}, t = {t.left}')
        res = False
        return res


    # check for right nodes
    if s.right and t.right:
        print('s.right and t.right exists')
        if s.right.val == t.right.val: # check if values are equal
            print('right nodes match')
            res = True
            # work on right subtree recursively
            compareBinTree(s.right,t.right)
        else:
            print(f'{s.right.val} is not equal to {t.right.val}')
            res = False
            return res

    if not s.right and not t.right:
        print('s.right and t.right both do not exits')
        res = True

    if (not s.right and t.right) or (s.right and not t.right):
        print('s and t do not match, s = {s.right}, t = {t.right}')
        res = False
        return res


    return res


r = compareBinTree(s, t)
print(r)