This post describes how to effectively use the `binarytree`

package for Python. Working with binary trees on LeetCode is a motivating use case for learning the package.

From the documentation home page:

Binarytreeis Python library which lets you generate, visualize, inspect and manipulate binary trees. Skip the tedious work of setting up test data, and dive straight into practising algorithms. Heaps and binary search trees are also supported. Self-balancing search trees like red-black or AVL will be added in the future.

It notes Python 3.7+ as a requirement for use of the package. The source code for the package may be found either on the package's GitHub page or its own documentation site.

## LeetCode

Arguably one of the biggest selling points for the `binarytree`

package is its ability to let you reproduce binary trees encountered when solving LeetCode problems. For example, consider LC 1026. Maximum Difference Between Node and Ancestor. We are told the definition for a binary tree node is as follows (this definition holds true for pretty much all LeetCode problems involving binary trees, except in some cases maybe `val`

does not have a default value, `left`

and `right`

may not default to `None`

, etc., but the structure is the same nonetheless):

`# Definition for a binary tree node.`

# class TreeNode:

# def __init__(self, val=0, left=None, right=None):

# self.val = val

# self.left = left

# self.right = right

The second example in the problem statement includes the following depiction of a binary tree:

How could we reproduce this tree using our own code? We could create our own `Node`

or `TreeNode`

class and *build* it ourselves by establishing the root and then linking together all nodes, but this becomes quite cumbersome as the tree grows (imagine encountering a test case for a tree with over a thousand nodes). Fortunately, there's a much better alternative for building such trees, namely using the `binarytree`

package.

The problem specifies as input the following for the tree above:

`root = [1,null,2,null,0,3]`

Can we somehow use this information to build the tree with the `binarytree`

package? Yes! As the site documentation notes for the `build2`

function:

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

Replace all instances of `null`

with `None`

for the root provided in the LeetCode input, and then use `build2`

to build the tree. We can then print the tree to see how it represents the image taken from LeetCode above:

`from binarytree import build2`

lc_tree = [1,None,2,None,0,3]

print(build2(lc_tree))

`1`

\

2__

\

0

/

3

A less compact way of building the tree above would be to use `build`

, where we need to provide the list representation of the binary tree, where the list of node values is generated by index for a left-to-right breadth-first order starting from the root:

`from binarytree import build`

lc_tree = [

1,None,2,None,None,None,0,None,

None,None,None,None,None,3

]

print(build(lc_tree))

`1`

\

2__

\

0

/

3

The easiest way to tell the difference between `build`

and `build2`

is how parent nodes play a role. For `build2`

, starting with `[1,None,2]`

indicates the left child of the root does not exist; thus, this cannot be the parent of any subsequent node. When we provide another value in our list, namely resulting in `[1,None,2,None]`

, this means `None`

becomes the left child of `2`

since `2`

can actually be a parent. Providing `0`

simply means `0`

is now the right child of `2`

. Continuing on, the only legitimate parent now is `0`

, which means providing a value of `3`

next results in `3`

being the left child of `1`

. Hence, we only have to provide `[1,None,2,None,0,3]`

to fully specify the tree.

The package documentation gives a more algebraic explanation for `binarytree.build2`

:

List of node values like those for

`binarytree.build()`

, but with a slightly different representation which associates two adjacent child values with the first parent value that has not been associated yet. This representation does not provide the same indexing properties where if a node is at index`i`

, its left child is always at`2i + 1`

, right child at`2i + 2`

, and parent at`floor((i - 1) / 2)`

, but it allows for more compact lists as it does not hold`None`

s between nodes in each level.

This is how LeetCode specifies its binary trees as input and allows for you to easily play around with possible tests cases.

## Package API specification

There's a lot more to the `binarytree`

package. More details and examples may be added to this blog post in the near future. Regardless, the documentation site for the package outlines in detail its API specification:

`binarytree.Node`

`binarytree.build()`

`binarytree.build2()`

`binarytree.tree()`

`binarytree.bst()`

`binarytree.heap()`

`binarytree.get_index()`

`binarytree.get_parent()`