Skip to content
Python Library for Studying Binary Trees
Python
Branch: master
Clone or download
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
binarytree Overhaul for 4.0 May 11, 2018
docs Update README and contributing.rst May 12, 2018
tests Overhaul for 4.0 May 11, 2018
.gitignore Add release version 1.0 Oct 8, 2016
.travis.yml Overhaul for 4.0 May 11, 2018
LICENSE Initial commit Sep 20, 2016
MANIFEST.in Overhaul for 4.0 May 11, 2018
README.rst Change 'Learning' to 'Studying' in project description for accuracy Jun 6, 2018
demo.gif Overhaul for 3.0 Dec 19, 2017
setup.cfg
setup.py Change 'Learning' to 'Studying' in project description for accuracy Jun 6, 2018

README.rst

Binarytree: Python Library for Studying Binary Trees

Build Status Package Version Python Versions Test Coverage Issues Open MIT License

Demo GIF

Introduction

Are you studying binary trees for your next exam, assignment or technical interview?

Binarytree is a Python library which provides a simple API to generate, visualize, inspect and manipulate binary trees. It allows you to skip the tedious work of setting up test data, and dive straight into practising your algorithms. Heaps and BSTs (binary search trees) are also supported.

Announcements

  • Binarytree version 4.0 is now out!
  • Please see the releases page for details on the latest updates.

Requirements

  • Python 2.7, 3.4, 3.5 or 3.6.

Installation

To install a stable version from PyPi:

~$ pip install binarytree

To install the latest version directly from GitHub:

~$ pip install -e git+git@github.com:joowani/binarytree.git@master#egg=binarytree

You may need to use sudo depending on your environment.

Getting Started

By default, binarytree uses the following class to represent a node:

class Node(object):

    def __init__(self, value, left=None, right=None):
        self.value = value  # The node value
        self.left = left    # Left child
        self.right = right  # Right child

Generate and pretty-print various types of binary trees:

>>> from binarytree import tree, bst, heap
>>>
>>> # Generate a random binary tree and return its root node
>>> my_tree = tree(height=3, is_perfect=False)
>>>
>>> # Generate a random BST and return its root node
>>> my_bst = bst(height=3, is_perfect=True)
>>>
>>> # Generate a random max heap and return its root node
>>> my_heap = heap(height=3, is_max=True, is_perfect=False)
>>>
>>> # Pretty-print the trees in stdout
>>> print(my_tree)
#
#        _______1_____
#       /             \
#      4__          ___3
#     /   \        /    \
#    0     9      13     14
#         / \       \
#        7   10      2
#
>>> print(my_bst)
#
#            ______7_______
#           /              \
#        __3__           ___11___
#       /     \         /        \
#      1       5       9         _13
#     / \     / \     / \       /   \
#    0   2   4   6   8   10    12    14
#
>>> print(my_heap)
#
#              _____14__
#             /         \
#        ____13__        9
#       /        \      / \
#      12         7    3   8
#     /  \       /
#    0    10    6
#

Use the binarytree.Node class to build your own trees:

>>> from binarytree import Node
>>>
>>> root = Node(1)
>>> root.left = Node(2)
>>> root.right = Node(3)
>>> root.left.right = Node(4)
>>>
>>> print(root)
#
#      __1
#     /   \
#    2     3
#     \
#      4
#

Inspect tree properties:

>>> from binarytree import Node
>>>
>>> root = Node(1)
>>> root.left = Node(2)
>>> root.right = Node(3)
>>> root.left.left = Node(4)
>>> root.left.right = Node(5)
>>>
>>> print(root)
#
#        __1
#       /   \
#      2     3
#     / \
#    4   5
#
>>> root.height
2
>>> root.is_balanced
True
>>> root.is_bst
False
>>> root.is_complete
True
>>> root.is_max_heap
False
>>> root.is_min_heap
True
>>> root.is_perfect
False
>>> root.is_strict
True
>>> root.leaf_count
3
>>> root.max_leaf_depth
2
>>> root.max_node_value
5
>>> root.min_leaf_depth
1
>>> root.min_node_value
1
>>> root.size
5

>>> root.properties  # To see all at once:
{'height': 2,
 'is_balanced': True,
 'is_bst': False,
 'is_complete': True,
 'is_max_heap': False,
 'is_min_heap': True,
 'is_perfect': False,
 'is_strict': True,
 'leaf_count': 3,
 'max_leaf_depth': 2,
 'max_node_value': 5,
 'min_leaf_depth': 1,
 'min_node_value': 1,
 'size': 5}

>>> root.leaves
[Node(3), Node(4), Node(5)]

>>> root.levels
[[Node(1)], [Node(2), Node(3)], [Node(4), Node(5)]]

Use level-order (breadth-first) indexes to manipulate nodes:

>>> from binarytree import Node
>>>
>>> root = Node(1)                  # index: 0, value: 1
>>> root.left = Node(2)             # index: 1, value: 2
>>> root.right = Node(3)            # index: 2, value: 3
>>> root.left.right = Node(4)       # index: 4, value: 4
>>> root.left.right.left = Node(5)  # index: 9, value: 5
>>>
>>> print(root)
#
#      ____1
#     /     \
#    2__     3
#       \
#        4
#       /
#      5
#
>>> # Use binarytree.Node.pprint instead of print to display indexes
>>> root.pprint(index=True)
#
#       _________0-1_
#      /             \
#    1-2_____        2-3
#            \
#           _4-4
#          /
#        9-5
#
>>> # Return the node/subtree at index 9
>>> root[9]
Node(5)

>>> # Replace the node/subtree at index 4
>>> root[4] = Node(6, left=Node(7), right=Node(8))
>>> root.pprint(index=True)
#
#       ______________0-1_
#      /                  \
#    1-2_____             2-3
#            \
#           _4-6_
#          /     \
#        9-7     10-8
#
>>> # Delete the node/subtree at index 1
>>> del root[1]
>>> root.pprint(index=True)
#
#    0-1_
#        \
#        2-3

Traverse the trees using different algorithms:

>>> from binarytree import Node
>>>
>>> root = Node(1)
>>> root.left = Node(2)
>>> root.right = Node(3)
>>> root.left.left = Node(4)
>>> root.left.right = Node(5)
>>>
>>> print(root)
#
#        __1
#       /   \
#      2     3
#     / \
#    4   5
#
>>> root.inorder
[Node(4), Node(2), Node(5), Node(1), Node(3)]

>>> root.preorder
[Node(1), Node(2), Node(4), Node(5), Node(3)]

>>> root.postorder
[Node(4), Node(5), Node(2), Node(3), Node(1)]

>>> root.levelorder
[Node(1), Node(2), Node(3), Node(4), Node(5)]

>>> list(root)  # Equivalent to root.levelorder
[Node(1), Node(2), Node(3), Node(4), Node(5)]

List representations are also supported:

>>> from binarytree import build
>>>
>>> # Build a tree from list representation
>>> values = [7, 3, 2, 6, 9, None, 1, 5, 8]
>>> root = build(values)
>>> print(root)
#
#            __7
#           /   \
#        __3     2
#       /   \     \
#      6     9     1
#     / \
#    5   8
#
>>> # Convert the tree back to list representation
>>> root.values
[7, 3, 2, 6, 9, None, 1, 5, 8]

Check out the documentation for more details!

Contributing

Please have a look at this page before submitting a pull request. Thanks!

You can’t perform that action at this time.