Trees

Trees are a data structure in which each element can have a descendant that represents an element of the same form.

In python tree can be defined as following class:

import random
from IPython.display import HTML
from copy import deepcopy

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

Particular realisatoin of the tree example in the cell below:

#    [1]
#  [2] [3]
head = Node(
    1,
    Node(2),
    Node(3)
)

Simple tree visualisation function. Interpretation of the result:

[Head node]
    [Left_1]
        [Left_l2]
        [Right_l2]
    [Right_1]
        [Left_r2]
        [Right_r2]

def print_tree(node, indent=0):
    if node is not None:
        print(f"{indent*' '}[{node.val}]")
        print_tree(node.left, indent+2)
        print_tree(node.right, indent+2)
    else:
        print(f"{indent*' '}[ ]")

head = Node(
    1,
    Node(
        2,
        Node(val=3),
        Node(val=4)
    ),
    Node(
        5,
        Node(val=6),
        Node(val=7)
    )
)
print_tree(head)

[1]
  [2]
    [3]
      [ ]
      [ ]
    [4]
      [ ]
      [ ]
  [5]
    [6]
      [ ]
      [ ]
    [7]
      [ ]
      [ ]

Here is funciton that generates random tree:

def gen_tree(p_left = 0.5, p_right = 0.5):
    '''
    Generate tree:

    Parameters
    ----------
    p_left : (float)
        probability to the node under consideration 
        is added node from the left;
    p_right : (flaot)
        probability to the node udner consideration
        is added node from the right side.
    '''
    return Node(
        val = random.randint(1, 100),
        left = (
            gen_tree(p_left, p_right) 
            if random.random() < p_left else
            None
        ),
        right = (
            gen_tree(p_left, p_right)
            if random.random() < p_right else
            None
        )
    )

random.seed(10)
head = gen_tree(p_left = 0.3, p_right = 0.3)
print_tree(head)

[74]
  [62]
    [ ]
    [63]
      [ ]
      [ ]
  [67]
    [ ]
    [96]
      [ ]
      [18]
        [ ]
        [ ]

Inorder

Traversal of the tree in order showed in the fllowing cell. “In order” means that the leftmost elements of the tree will always be processed first.

Extracting element

So here is example that adds elements to a sequential array:

def inorder(root : Node, res):
    if root is not None:
        inorder(root.left, res)
        res.append(root.val)
        inorder(root.right,res)
    return res

And use of the funtion:

head = Node(1, 
    Node(5, Node(7), Node(8)), 
    Node(6, Node(9), Node(10))
)
print_tree(head)
inorder(head, [])

[1]
  [5]
    [7]
      [ ]
      [ ]
    [8]
      [ ]
      [ ]
  [6]
    [9]
      [ ]
      [ ]
    [10]
      [ ]
      [ ]

[7, 5, 8, 1, 9, 6, 10]

Comparison of trees

Here is algorithm for trees comparison base on inorder.

def are_trees_equal(head1, head2):
    # here is 
    if (head1 is None) != (head2 is None):
        return False
    if (head1 is None):
        return True
    if head1.val != head2.val:
        return False
    return all([
        are_trees_equal(head1.left, head2.left),
        are_trees_equal(head1.right, head2.right)
    ])

In the following cell three trees are created. The first and second are different, but the third is just a copy of the first.

random.seed(10)
tree1 = gen_tree(0.3, 0.3)
display(HTML("<p style='font-size:16px'>Tree 1</p>"))
print_tree(tree1)

tree2 = gen_tree(0.3, 0.3)
display(HTML("<p style='font-size:16px'>Tree 2</p>"))
print_tree(tree2)

tree3 = deepcopy(tree1)
display(HTML("<p style='font-size:16px'>Tree 3</p>"))
print_tree(tree3)

Tree 1

[74]
  [62]
    [ ]
    [63]
      [ ]
      [ ]
  [67]
    [ ]
    [96]
      [ ]
      [18]
        [ ]
        [ ]

Tree 2

[37]
  [ ]
  [23]
    [ ]
    [ ]

Tree 3

[74]
  [62]
    [ ]
    [63]
      [ ]
      [ ]
  [67]
    [ ]
    [96]
      [ ]
      [18]
        [ ]
        [ ]

Here is the result of the application function under consideration.

print(
    "Tree1==Tree2 -", 
    are_trees_equal(tree1, tree2)
)
print(
    "Tree1==Tree3 -",
    are_trees_equal(tree1, tree3)
)

Tree1==Tree2 - False
Tree1==Tree3 - True