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

class BinarySearchTreeNode:
    def __init__(self, key):
        self.key = key
        self.right = None
        self.left = None

    def insert(self, key):
        if self.key == key:
            return

        if self.key < key:
            if self.right is None:
                self.right = BinarySearchTreeNode(key)
            else:
                self.right.insert(key)
        else: # key < self.key:
            if self.left is None:
                self.left = BinarySearchTreeNode(key)
            else:
                self.left.insert(key)

    # ref: https://stackoverflow.com/questions/34012886/print-binary-tree-level-by-level-in-python
    def display(self):
        lines, *_ = self._display()
        for line in lines:
            print(line)

    def _display(self):
        """Returns list of strings, width, height, and horizontal coordinate of the root."""
        # No child.
        if self.right is None and self.left is None:
            line = '%s' % self.key
            width = len(line)
            height = 1
            middle = width // 2
            return [line], width, height, middle

        # Only left child.
        if self.right is None:
            lines, n, p, x = self.left._display()
            s = '%s' % self.key
            u = len(s)
            first_line = (x + 1) * ' ' + (n - x - 1) * '_' + s
            second_line = x * ' ' + '/' + (n - x - 1 + u) * ' '
            shifted_lines = [line + u * ' ' for line in lines]
            return [first_line, second_line] + shifted_lines, n + u, p + 2, n + u // 2

        # Only right child.
        if self.left is None:
            lines, n, p, x = self.right._display()
            s = '%s' % self.key
            u = len(s)
            first_line = s + x * '_' + (n - x) * ' '
            second_line = (u + x) * ' ' + '\\' + (n - x - 1) * ' '
            shifted_lines = [u * ' ' + line for line in lines]
            return [first_line, second_line] + shifted_lines, n + u, p + 2, u // 2

        # Two children.
        left, n, p, x = self.left._display()
        right, m, q, y = self.right._display()
        s = '%s' % self.key
        u = len(s)
        first_line = (x + 1) * ' ' + (n - x - 1) * '_' + s + y * '_' + (m - y) * ' '
        second_line = x * ' ' + '/' + (n - x - 1 + u + y) * ' ' + '\\' + (m - y - 1) * ' '
        if p < q:
            left += [n * ' '] * (q - p)
        elif q < p:
            right += [m * ' '] * (p - q)
        zipped_lines = zip(left, right)
        lines = [first_line, second_line] + [a + u * ' ' + b for a, b in zipped_lines]
        return lines, n + m + u, max(p, q) + 2, n + u // 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

def build_minimum_height_bst(keys):
    return _build_minimum_height_bst(keys, 0, len(keys) - 1)

def _build_minimum_height_bst(keys, start, end):
    if end < start:
        return None

    middle = (start + end) // 2
    root = BinarySearchTreeNode(keys[middle])
    root.left = _build_minimum_height_bst(keys, start, middle - 1)
    root.right = _build_minimum_height_bst(keys, middle + 1, end)

    return root

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

def list_of_depths(root, lsts, level):
    if root is None:
        return

    lst = None
    if len(lsts) == level: # 深さ0のリストの存在に注意
        lst = []
        lsts.append(lst)
    else:
        lst = lsts[level]
    lst.append(root.key)
    list_of_depths(root.left, lsts, level + 1)
    list_of_depths(root.right, lsts, level + 1)

    return lsts

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

def list_of_depths(root):
    if root is None:
        return []

    suspended = []
    suspended.append(root)

    lsts = []
    level = 0

    while len(suspended) != 0:
        if len(lsts) == level:
            lsts.append([])
        next_suspended = []
        for u in suspended:
            lsts[level].append(u.key)
            if u.left is not None:
                next_suspended.append(u.left)
            if u.right is not None:
                next_suspended.append(u.right)
        suspended = next_suspended
        level += 1

    return lsts

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

def get_height(root):
    # base case
    if root is None:
        return -1

    left = get_height(root.left)
    right = get_height(root.right)

    return max(left, right) + 1

def is_balanced(root):
    if root is None:
        return true
    diff = abs(get_height(root.left) - get_height(root.right))
    if 1 < diff:
        return False
    else:
        return is_balanced(root.left) and is_balanced(root.right)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Integer:
    def __init__(self, num):
        self.num = num

last_visited = None
def is_valid(root):
    if root is None:
        return True

    if not is_valid(root.left):
        return False

    if last_visited is not None and root.key <= last_visited.num:
        return False

    if not is_valid(root.right):
        return False

    return True

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

def inorder(root):
    if root is None:
        return
    inorder(root.left)
    print(root.key)
    inorder(root.right)

def preorder(root):
    if root is None:
        return
    print(root.key)
    preorder(root.left)
    preorder(root.right)

def postorder(root):
    if root is None:
        return
    postorder(root.left)
    postorder(root.right)
    print(root.key)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

def left_most_child(root):
    if root is None:
        return None
    while root.left is not None:
        root = root.left
    return root

def inorder_successor(root):
    if root is None:
        return None

    if root.right is not None:
        return left_most_child(root.right)
    else:
        q = root
        x = root.parent
        while x is not None and q is not x.left:
            q = x
            x = q.parent
        return x