Talk with You Series #3

Intro

Today we gonna cover the theoretical and practical foundations of Binary Tree as well as the ways to traverse it.

Tree, in general, is the subset of graphs family, which follow certain rules within their construction and management.

Binary Trees

Binary Tree is a concrete data structure in which each node has at most two children. Commonly every node has 3 attributes: data, leftChild and rightChild.

It is used to classify Binary Tree with different types by their "criteria".

Let's see which types (classes) exists out there:

1. Types of Binary Tree based on the number of children (criteria: node number of children)
2. Types of Binary Tree on the basis of the completion of levels (criteria: tree completion of levels)
3. Types of Binary Tree on the basis of the node values (criteria: node values)

Let's have a look at each type separately.

Types of Binary Tree based on the number of children

• Full Binary Tree
• Degenerate (or pathological) tree
• Skewed Binary Tree

Types of Binary Tree on the basis of the completion of levels

• Complete Binary Tree
• Perfect Binary Tree
• Balanced Binary Tree

Types of Binary Tree on the basis of the node values

• Binary Search Tree
• AVL Tree
• Red Black Tree
• B Tree
• B+ Tree
• Segment Tree

If you d like to dig deeper about each of them, here's complete overview.

Good, now we have an understanding what is Binary Tree conceptually as well as what might be the types.

Now, let's code it up. To recall, Binary Tree consists of nodes, where each node has data, leftChild and rightChild properties.

from typing import Any

class TreeNode:
    def __init__(self, data: Any):
        self.data = data
        self.left = None
        self.right = None

# define all the nodes we need
root = TreeNode('R')
nodeA = TreeNode('A')
nodeB = TreeNode('B')
nodeC = TreeNode('C')
nodeD = TreeNode('D')

# connect all the nodes between each other
root.left = nodeA
root.right = nodeB
nodeA.left = nodeC
nodeA.right = nodeD

# what we've got
    R
   / \
  A   B
 / \ 
C   D

The next thing which is crucial - how to traverse Binary Tree.

Traverse Binary Tree

Commonly, there are 2 main ways (types) to traverse Binary Tree, Breadth First Search (BFS) and Depth First Search (DFS).

• BFS stands for when the nodes on the same level are visited before going to the next level in the tree. This means that the tree is explored in a more sideways direction.

• DFS stands for when the traversal moves down the tree all the way to the leaf nodes, exploring the tree branch by branch in a downwards direction.

Additionally, there are three types of DFS traversals:

• pre-order
• post-order
• in-order

DFS and it's types of traversal

"""
preOrder - is done by visiting the root node first, then recursively do a pre-order traversal of the left subtree, followed by a recursive pre-order traversal of the right subtree.

This traversal is "pre" order because the node is visited "before" the recursive pre-order traversal of the left and right subtrees.
"""

def pre_order(node):
    if node:
        print(node.value)
        pre_order(node.left)
        pre_order(node.right)

"""
postOrder - works by recursively doing a Post-order Traversal of the left subtree and the right subtree, followed by a visit to the root node.

What makes this traversal "post" is that visiting a node is done "after" the left and right child nodes are called recursively.
"""

def post_order(node):
    if node:
        post_order(node.left)
        post_order(node.right)
        print(node.value)

"""
inOrder - does a recursive In-order Traversal of the left subtree, visits the root node, and finally, does a recursive In-order Traversal of the right subtree.

What makes this traversal "in" order, is that the node is visited in between the recursive function calls. The node is visited after the In-order Traversal of the left subtree, and before the In-order Traversal of the right subtree.
"""

def in_order(node):
    if node:
        in_order(node.left)
        print(node.value)
        in_order(node.right)

That's it for today. Wrapping, we've revamped what is Binary Tree, it's types split by criteria and what are the ways to traverse it.