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:
Types of Binary Tree based on the number of children (criteria: node number of children)
Types of Binary Tree on the basis of the completion of levels (criteria: tree completion of levels)
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.
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.
