LeetCode Trees

Mar 27, 2022 | 3 min read | technical

A package to provide a convenient way to manually input binary trees using LeetCode’s level order traversal with None-path-termination serialization format. Also, a function to print binary trees to the terminal as ASCII characters.

Binary Trees

A binary tree is a well-known data structure used in computer science. It consists of nodes that are each connected to up to two children nodes, and each node keeps track of the references to its children and its assigned value. Binary trees are used in many classes of algorithms such as searches and sorts, and they also appear as machine learning models in the form of decision trees. They are also frequently tested in coding interviews since they provide a convenient way to probe a candidate’s knowledge of recursion and their problem solving skills.

A binary tree. (Wikipedia)

Serializing a Binary Tree

While playing around with some LeetCode problems, I encountered their approach to serializing binary trees into lists of values. Essentially, the desired values of the nodes are listed in a level order traversal, but Nones are used to indicate the lack of a child node where one would have been possible.

For example, the above tree would be serialized as:

serialized_tree = [2, 7, 5, 2, 6, None, 9, None, None, 5, 11, 4]

This is a fairly efficient way to input a binary tree structure, at least for a human. This is more compact than typical level order (breadth-first) traversal serialization where additional Nones would be specified even when the paths through their parents were already terminated. Such a serialization would look like:

verbose_serialized_tree = [2, 7, 5, 2, 6, None, 9, None, None, 5, 11, None, None, 4, None]

and the inefficiency would increase with depth if the tree is far from being full.

Most painful of all would be inputting a tree in its native representation. For example, if we wanted to construct this tree directly with TreeNode objects, it would look something like this:

node_a = TreeNode(val=5)
node_b = TreeNode(val=11)
node_c = TreeNode(val=4)
node_d = TreeNode(val=2)
node_e = TreeNode(val=6, left=node_a, right=node_b)
node_f = TreeNode(val=9, left=node_c)              
node_g = TreeNode(val=7, left=node_d, right=node_e)
node_h = TreeNode(val=5, right=node_f)
root = TreeNode(val=2, left=node_g, right=node_h)

It is a verbose and tedious form of constructing the tree, and prone to errors.

A Simple Package for Deserializing Binary Trees and Printing Them

Deserializing the previous binary tree and printing it with ASCII.

I put together a python package called leetcode-trees on GitHub.

It has a function for constructing trees given the LeetCode serialized list of values, and a function for printing a tree directly to terminal given the root node. This can be convenient for quickly checking what a constructed tree looks like, without graphical overhead.

Installation

The simplest way to use the package is to install it with pip,

pip install git+https://github.com/cflamant/leetcode-trees.git

Examples

input:

from leetcode_trees.binarytree import tree_from_list, print_tree
a = tree_from_list(list(range(15)))
print_tree(a)

output:

Tree a.

input:

b = tree_from_list(['a','b','c',None,'d','e','f',None,None,'g','h','i'])
print_tree(b)

output:

Tree b.

input:

c = tree_from_list([
    "long","string","reps","work", None,
    "reasonably", None, "well","too","as",
    "the","text","is","centered"
])
print_tree(c)