Binary Trees

Introduction

• A binary tree is a type of tree in which each node has at most two child branches.
• These child branches are labelled left and right.

Example

Internal and External Nodes

• Internal nodes:
  • An internal node is a node that has children.
  • In the example below there are 4 internal nodes.
  • The internal path length is the sum of the levels of all the internal nodes.
  • In the example below the internal path length is: 1 + 1 + 2 = 4.
• External nodes:
  • An external node is a node that does not have children.
  • It is also called a leaf node.
  • In the example below there are 4 external nodes.
  • The external path length is the sum of hte levels of all the external nodes.
  • In the example below the external path length is: 2 + 2 + 3 + 3 = 10.
• Example:
  • The internal nodes are colored red.
  • The external nodes are colored blue.

Full Binary Tree

• A full binary tree is a type of binary tree in which each node has exactly 0 or 2 child branches.
• They are also called proper binary trees or plane binary trees.
• Example:

Extended Binary Tree

• An extended binary tree is a type of full tree
• It is created by extending nodes of an existing tree:
  • If the existing node has no children then two child nodes are added
  • If the existing node has 1 child then a second child is added
• Example:
  • The existing nodes are drawn as blue circles
  • The new, extended nodes are drawn as red rectangles

Complete Binary Tree

• A complete tree is a type of binary tree in which every node as two children apart from the bottom level, which is filled from left to right.
• Example:
• Complete binary trees are useful because they offer the best ratio between the height and the number of nodes.

Perfect Binary Tree

• A binary tree is perfect if all of the external nodes are on the same level.
• Example:

Skewed Binary Tree

• A skewed binary tree is a tree which is dominated by either left or right nodes.
• Example:

Code (Python)

# -*- coding: utf-8 -*-

class Node:
    def __init__(self, data):
        self.data = data

    def addLeft(self, node):
        node = node if isinstance(node, Node) else Node(node)
        self.left = node
        node.parent = self
        return self # returns self so it can be chained

    def addRight(self, node):
        node = node if isinstance(node, Node) else Node(node)
        self.right = node
        node.parent = self
        return self
    
    def __str__(self, path = '', last = True):
        ret = path + ('' if not path else ('└─ ' if last else '├─ ')) + self.data + '\n'
        
        if hasattr(self, 'left'):
            ret += self.left.__str__(path + ('   ' if last else '│  '), False)
        elif hasattr(self, 'right'):
            #we use a fake node for spacing
            ret += Node("").__str__(path + ('   ' if last else '│  '), False)
        
        if hasattr(self, 'right'):
            ret += self.right.__str__(path + ('   ' if last else '│  '), True)
        elif hasattr(self, 'left'):
            ret += Node("").__str__(path + ('   ' if last else '│  '), True)
        
        return ret

Usage:

tree = \
    Node("Colors") \
        .addLeft(Node("Blue")
            .addRight("Dark Blue")) \
        .addRight(Node("Red")
            .addLeft("Light Red")
            .addRight("Dark Red")) \

print(tree)

Output:

Colors
├─ Blue
│  ├─ 
│  └─ Dark Blue
└─ Red
    ├─ Light Red
    └─ Dark Red