Featured image of post SP3 - Tree - Learn Design Pattern From Simple Things

SP3 - Tree - Learn Design Pattern From Simple Things

You need to store the leaves hierarchically, sometimes you will count the leaves. Tree will be a suitable structure to facilitate leaf counting.

Tree (Composite) is a structural design pattern: šŸ–¤šŸ–¤šŸ–¤šŸ–¤šŸ–¤

What is Tree?

Tree is an object that contains Branches and Leaves. We can recursively over the whole tree structure and sum up the results easily.

Tree diagram

Why use Tree?

It’s neat and clean as you traverse the entire tree to find what you need. You have no choice but it!

Tree branches

Question: Branch is like a container, right? How about using the list to store leaves?

Answer: Branch is like a container, but it has a method(def operation, Same name as leaf’s method) that can delegate the work to all leaves in it. Thus, it is possible to traverse all the leaf’s methods(operations)

When to use Tree?

Question: When do I need to use Tree?

Answer: When you want to store the leaves hierarchically. Then want to traverse and use the method of leaves(operations)?

Input:

  • Having many leaves.
  • Having the hierarchy of those leaves.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Leaf:
    def operation(self):
        return "šŸ"

container_1 = []
container_1.append(Leaf())
container_1.append(Leaf())
container_2 = []
container_2.append(Leaf())
wormy_leaf = Leaf()

containers = []
containers.append(container_1)
containers.append(Leaf())
containers.append(wormy_leaf)
containers.append(container_2)
containers.remove(wormy_leaf)

Expected Output:

  • All leaves are stored hierarchically in an object
  • Show the operation of all leaves
1
[['šŸ', 'šŸ'], 'šŸ', ['šŸ']]

How to implement Tree?

Non-Tree implementation:

 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
class Leaf:
    def operation(self):
        return "šŸ"


def platten(nested_list):
    results = []
    for item in nested_list:
        item_result = platten(item) if isinstance(item, list) else item.operation()
        results.append(item_result)
    return results


if __name__ == "__main__":
    container_1 = []
    container_1.append(Leaf())
    container_1.append(Leaf())

    container_2 = []
    container_2.append(Leaf())

    wormy_leaf = Leaf()

    containers = []
    containers.append(container_1)
    containers.append(Leaf())
    containers.append(wormy_leaf)
    containers.append(container_2)
    containers.remove(wormy_leaf)

    print(platten(containers))

Tree Implementation:

 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
from abc import ABC, abstractmethod


class Component(ABC):
    _parent = None

    @property
    def parent(self):
        return self._parent

    @parent.setter
    def parent(self, parent):
        self._parent = parent

    def add(self, component):
        pass

    def remove(self, component):
        pass

    @abstractmethod
    def operation(self):
        pass


class Leaf(Component):
    """
    A leaf can't have any children.
    Leaf objects do the actual work.
    """

    def operation(self):
        return "šŸ"


class Branch(Component):
    """
    A branch can have children(leaves or baby branches) .
    Branch objects do nothing but contain children
    """

    def __init__(self):
        self._children = []

    def add(self, component):
        component.parent = self
        self._children.append(component)

    def remove(self, component):
        component.parent = None
        self._children.remove(component)

    def operation(self):
        results = []
        for child in self._children:
            results.append(child.operation())
        return results


if __name__ == "__main__":
    branch_1 = Branch()
    branch_1.add(Leaf())
    branch_1.add(Leaf())

    branch_2 = Branch()
    branch_2.add(Leaf())

    wormy_leaf = Leaf()

    tree = Branch()
    tree.add(branch_1)
    tree.add(Leaf())
    tree.add(wormy_leaf)
    tree.add(branch_2)
    tree.remove(wormy_leaf)

    print(tree.operation())

Source Code

Made with the laziness šŸ¦„
by a busy guy