OverviewΒΆ

Binarytree uses the following class to represent a node:

class Node:

    def __init__(self, value, left=None, right=None):
        self.value = value  # The node value (float/int/str)
        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

Generate trees with letter values instead of numbers:

>>> from binarytree import tree

>>> my_tree = tree(height=3, is_perfect=False, letters=True)

>>> print(my_tree)

      ____H____
     /         \
  __E__         F__
 /     \       /   \
M       G     J     B
 \     /     /     / \
  O   L     D     I   A

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

>>> properties = root.properties  # Get all properties at once.
>>> properties['height']
2
>>> properties['is_balanced']
True
>>> properties['max_leaf_depth']
2

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

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

Compare and clone trees:

>>> from binarytree import tree
>>> original = tree()
>>> clone = original.clone()
>>> original.equals(clone)
True

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 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)]

Convert to List representations:

>>> 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]

Binarytree supports another representation which is more compact but without the indexing properties (this method is often used in Leetcode):

>>> from binarytree import build, build2, Node
>>>
>>> # First let's create an example tree.
>>> root = Node(1)
>>> root.left = Node(2)
>>> root.left.left = Node(3)
>>> root.left.left.left = Node(4)
>>> root.left.left.right = Node(5)
>>> print(root)

        1
       /
    __2
   /
  3
 / \
4   5


>>> # First representation is already shown above.
>>> # All "null" nodes in each level are present.
>>> root.values
[1, 2, None, 3, None, None, None, 4, 5]

>>> # Second representation is more compact but without the indexing properties.
>>> root.values2
[1, 2, None, 3, None, 4, 5]

>>> # Build trees from both list representations.
>>> tree1 = build(root.values)
>>> tree2 = build2(root.values2)
>>> tree1.equals(tree2)
True

See API Specification for more details.