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.