Binary Trees

Prerequisites

Trees Show

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

Example of a binary tree.

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: Example of a binary tree with internal and external nodes.
    • 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: Example of a full binary tree.

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: Example of an extended binary tree
    • 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: Example of a complete binary tree.
  • 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: Example of a perfect binary tree.

Skewed Binary Tree

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

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