Hi there,
I did not get the reason why the value of Node class in binarytree must be integer in the new version (3.0.1.), whereas it worked perfectly for floating point value in the old version (1.1.1).
Can you fix that?
Thanks
MC

Hi,

I'm new to github but I just found your project, which really interests me and should make my work easier.

I've read through the documentation, and I didn't find a way to associate strings to a Node. I actually need it to process the Huffman algorithm, and therefore need to create a tree with each letters of my message and their probability. I've spotted the value of the node could be a float, which fits for the probability, but have you thought about a way to implement strings ?

I could maybe use ASCII to put integers in place of letters in the tree, but that would require me to attach the weight (probability) to such a node and I did not find out if that was possible either.

Could you help me better understanding your library ?
Thank you very much !

Tree:

    5 
  /    \
2       3
       /   \
      2     4
     / \
    3   1

Code:

from binarytree import build
li = [5, 2, 3, None, None, 2, 4, 3, 1]
build(li)

Error:

File "C:\Program Files\Python37\lib\site-packages\binarytree\__init__.py", line 1811, in build
    'parent node missing at index {}'.format(parent_index))

FYI:

def build(values):
    ...
    nodes = [None if x is None else Node(x) for x in data]
    non_null_nodes = [x for x in nodes if x is not None]
    for i in range(1, len(nodes)):
        if nodes[i] is not None:
            parent_index = (i - 1) // 2
            parent = non_null_nodes[parent_index]
    ...

def levelorder(self):
    ...
    current_level = [self]
    res = []
    while current_level:
        next_level = []
        for node in current_level:
            if node:
                res.append(node.val)
                next_level.append(node.left)
                next_level.append(node.right)
            else:
                res.append(None)
        current_level = next_level
    while res:
        if res[-1] is None:
            res.pop()
        else:
            break
    return res

The function _is_balanced always returns 1 + height. What gives?

import binarytree
ttree = binarytree.tree(height=3, is_perfect=True)
print(ttree)
assert ttree.height == binarytree._is_balanced(ttree), \
f'Tree property height: {ttree.height} is not equal to \
_is_balanced function return value: {binarytree._is_balanced(ttree)}' 

You can also visit https://repl.it/@ashokb/binarytreeBalanced to run it

Hi, and first thanks for this handy package. I'm using it with my students, and even if I really like the print method, I would like to have better outputs as I am using it on notebooks.

I've implemented a regular tree display in svg format. It allows outputs like this:

Are you interested in this feature, it do not change anything except in notebooks, where the traditionnal print method will still work.

For reference here is the doc for _repr_svg_:

https://ipython.readthedocs.io/en/stable/config/integrating.html?highlight=repr_svg#rich-display

First of all nice package, thanks for that! I just wanted to visualize a binary tree with Graphviz thats why I adapted this utility function from the treelib package, maybe it fits somewhere in your library. As I wanted to have string values for nodes and that doesn't work with your package I supplied an optional id2name dictionary, which stores the mapping.

import binarytree as bt

def binarytree_to_dot(root: bt.Node, filename: str, id2name: Optional[Dict[int, str]] = None, 
                      shape: str = 'ellipse', graph: str = 'digraph') -> None:
    """Exports the tree in dot format of the graphviz software. 
    Left childs are denoted by a full stroke arrow, right childs by a dashed arrow."""

    if not isinstance(root, bt.Node):
        raise ValueError("Root must be a binarytree.")
        
    if id2name is None:
        id2name = {node.value: str(node.value) for node in root}
        
    nodes, connections = [], []
    
    for node in root.levelorder:
        nid = node.value
        state = '"' + str(nid) + '"' + ' [label="' + str(id2name[nid]) + '", shape=' + shape + ']'
        nodes.append(state)

        if node.left is not None:
            cid = node.left.value
            connections.append('"' + str(nid) + '":sw' + ' -> ' + '"' + str(cid) + '"')
        if node.right is not None:
            cid = node.right.value
            connections.append('"' + str(nid) + '":se' + ' -> ' + '"' + str(cid) + '"  [style=dashed]')

    # write nodes and connections to dot format
    with open(filename, 'wt') as f:
        f.write(graph + ' tree {\n')
        for n in nodes:
            f.write('\t' + n + '\n')

        f.write('\n')
        for c in connections:
            f.write('\t' + c + '\n')

        f.write('}')

Example Use

Use it like this

root = bt.tree(height=6)
binarytree_to_dot(root, filename="test_tree.dot")

After installing graphviz, you can plot the tree with the following command:

dot -T png -o test_tree.png test_tree.dot

which will result in the following image:

Summary

while trying to repr tree as image following the example provided on readme, got following error:

AttributeError: 'Digraph' object has no attribute '_repr_svg_'

looks like it's because Digraph._repr_svg_() is deprecated:

and is solved by replacing the line with:

return self.graphviz()._repr_image_svg_xml()

(_repr_image_svg_xml() returns str)

Log

text:

from binarytree import tree
t = tree()
t
---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
File ~/.asdf/installs/python/3.10.1/lib/python3.10/site-packages/IPython/core/formatters.py:343, in BaseFormatter.__call__(self, obj)
    [341](file:///home/scarf/.asdf/installs/python/3.10.1/lib/python3.10/site-packages/IPython/core/formatters.py?line=340)     method = get_real_method(obj, self.print_method)
    [342](file:///home/scarf/.asdf/installs/python/3.10.1/lib/python3.10/site-packages/IPython/core/formatters.py?line=341)     if method is not None:
--> [343](file:///home/scarf/.asdf/installs/python/3.10.1/lib/python3.10/site-packages/IPython/core/formatters.py?line=342)         return method()
    [344](file:///home/scarf/.asdf/installs/python/3.10.1/lib/python3.10/site-packages/IPython/core/formatters.py?line=343)     return None
    [345](file:///home/scarf/.asdf/installs/python/3.10.1/lib/python3.10/site-packages/IPython/core/formatters.py?line=344) else:

File ~/.asdf/installs/python/3.10.1/lib/python3.10/site-packages/binarytree/__init__.py:512, in Node._repr_svg_(self)
    [506](file:///home/scarf/.asdf/installs/python/3.10.1/lib/python3.10/site-packages/binarytree/__init__.py?line=505) """Display the binary tree using Graphviz (used for `Jupyter notebooks`_).
    [507](file:///home/scarf/.asdf/installs/python/3.10.1/lib/python3.10/site-packages/binarytree/__init__.py?line=506) 
    [508](file:///home/scarf/.asdf/installs/python/3.10.1/lib/python3.10/site-packages/binarytree/__init__.py?line=507) .. _Jupyter notebooks: https://jupyter.org
    [509](file:///home/scarf/.asdf/installs/python/3.10.1/lib/python3.10/site-packages/binarytree/__init__.py?line=508) """
    [510](file:///home/scarf/.asdf/installs/python/3.10.1/lib/python3.10/site-packages/binarytree/__init__.py?line=509) try:
    [511](file:///home/scarf/.asdf/installs/python/3.10.1/lib/python3.10/site-packages/binarytree/__init__.py?line=510)     # noinspection PyProtectedMember
--> [512](file:///home/scarf/.asdf/installs/python/3.10.1/lib/python3.10/site-packages/binarytree/__init__.py?line=511)     return str(self.graphviz()._repr_svg_())
    [514](file:///home/scarf/.asdf/installs/python/3.10.1/lib/python3.10/site-packages/binarytree/__init__.py?line=513) except (SubprocessError, ExecutableNotFound, FileNotFoundError):
    [515](file:///home/scarf/.asdf/installs/python/3.10.1/lib/python3.10/site-packages/binarytree/__init__.py?line=514)     return self.svg()

AttributeError: 'Digraph' object has no attribute '_repr_svg_'
Node(3)

screenshot:

Versions

ubuntu 21.10
python 3.10.1
ipython 8.1.1
binarytree 6.5.1
graphviz 0.20

hello i am new in github and though i have already installed the package by using "pip install binarytree", I still wonder why I downloaded the zip and ran "pip setup.py install" but went wrong with the error "setuptools-scm was unable to detect version for C:\Users\Desktop\binarytree-6.5.1." while I have installed setuptools-scm package in version of 8.0.4. Thanks a lot!

[1, 2, 3, None, None, 5, 6, 7, 8, 9, None, None, None, 10, None, 11] should produce:

[2, 5, None, 3, None, 1, 4] should produce:

but both fail.

                if parent is None:
>                   raise NodeNotFoundError(
                        "parent node missing at index {}".format(parent_index)
                    )
E                   binarytree.exceptions.NodeNotFoundError: parent node missing at index 3

/Users/me/.pyenv/versions/3.9.2/lib/python3.9/site-packages/binarytree/__init__.py:2008: NodeNotFoundError

Whereas the following code builds the trees as expected:

def from_list(nums: Sequence[Optional[int]]) -> Optional[TreeNode]:
    """Build a binary tree in level order.
    The idea is to take two numbers and associate with the first non-null parent that hasn't been looked at.

    Keyword arguments:
    nums -- node values
    """
    queue: collections.deque[TreeNode] = collections.deque()
    root = None
    if nums:
        root = TreeNode(nums[0])
        queue.append(root)
    i = 1

    while i < len(nums):
        node = queue.popleft()
        if nums[i] is not None:
            node.left = TreeNode(nums[i])
            queue.append(node.left)
        i += 1
        if i < len(nums) and nums[i] is not None:
            node.right = TreeNode(nums[i])
            queue.append(node.right)
        i += 1

    queue.clear()
    return root

I met a problem when implementing the morris traversal algorithm using this package, the simplified code is as follows:

from binarytree import build

# morris traversal algorithm will cause circular references
# but it will be solved while traveling again
def cycle(root):
    condition = True

    while root:
        if condition:
            root.right = root
            condition = False

        else:
            root.right = None


if __name__ == '__main__':
    node = build([1,2,3,4,5])
    cycle(node)

the while statement will call the root.__len__(), which will get size by level traversal. But if there is a circular references like above, level traversal will get into infinite loop without any message about it. Changing the while statement to while root is not None can solve this, but I think it would be better to raise some message if this happened.

Suggestions:

1. len(node) can get correct size of node even though there is circular references.
   you can use set to record the visited node while counting size of node using level traversal. Besides, while node, if node looks more graceful than while node is not None, if node is not None.

2. if the first proposal is rejected, please raise some error message or warning while get into len(node) infinite loop.

It would be nice to have a way to set the seed (or random state) for creating random trees. For instance, something like bst(4, random_state=42) would return always the same random tree.

Thanks!

Documentation is missing explanation if this data structure keeps the data balanced (red-black, AVL) or not.

If it's NOT, better to explicitly say in the very first few lines of the readme.

Hello, i think that a short reference for the properties of binary trees will be useful for the purpose of the project.
Something like :

what_is_full()
Is a tree in which every node in the tree has either 0 or 2 children.
An Example

Hi! Could we add a requirements.txt file for making it easy for new contributors to contribute?

Hi, I find this project superb cool. I read through the code in the first time. All code are concise and good. But I am having a hard time trying to understand the algorithm to pretty-print(pprint) the tree.

Can you add more comments to explain how it works? It seems the code is building up the node value and formatting ascii strings level by level. But I am very curious about the idea behind, like what does l_len, l_vale_from, l_anhor works? what l_anchor is marked as ceiling and r_anchor as floor?

def _build_str(node):
    """Helper function used for pretty-printing."""
    if node == _null:
        return 0, 0, 0, []

    line1 = []
    line2 = []
    val_len = gap_len = len(str(_value_of(node)))

    l_len, l_val_from, l_val_to, l_lines = _build_str(_left_of(node))
    r_len, r_val_from, r_val_to, r_lines = _build_str(_right_of(node))

    if l_len > 0:
        l_anchor = -int(-(l_val_from + l_val_to) / 2) + 1  # ceiling
        line1.append(' ' * (l_anchor + 1))
        line1.append('_' * (l_len - l_anchor))
        line2.append(' ' * l_anchor + '/')
        line2.append(' ' * (l_len - l_anchor))
        val_from = l_len + 1
        gap_len += 1
    else:
        val_from = 0

    line1.append(str(_value_of(node)))
    line2.append(' ' * val_len)

    if r_len > 0:
        r_anchor = int((r_val_from + r_val_to) / 2)  # floor
        line1.append('_' * r_anchor)
        line1.append(' ' * (r_len - r_anchor + 1))
        line2.append(' ' * r_anchor + '\\')
        line2.append(' ' * (r_len - r_anchor))
        gap_len += 1
    val_to = val_from + val_len - 1

    gap = ' ' * gap_len
    lines = [''.join(line1), ''.join(line2)]
    for i in range(max(len(l_lines), len(r_lines))):
        l_line = l_lines[i] if i < len(l_lines) else ' ' * l_len
        r_line = r_lines[i] if i < len(r_lines) else ' ' * r_len
        lines.append(l_line + gap + r_line)

    return len(lines[0]), val_from, val_to, lines

When importing I get the error:
No module named 'graphviz.exceptions'

I did the pip install with both graphviz and binarytree and I have the last version of both. Python version: 3.7

Hi, I'm the package maintainer for binarytree on the AUR.

With release 6.5.0, I noticed that the graphviz imports changed to fetch ExecutableNotFound from graphviz.exceptions, but to my knowledge, ExecutableNotFound still exists under graphviz.

Was this a mistake? I tested this against graphviz 0.19.

The license states that it should be packaged in all distributions of the package, but it is not packaged in the pypi release. I only realized this because I am in the process of packaging bonarytree for conda forge.

Hi,
I was looking at documentation for building a tree from list. Below is from the documentation,

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

Then I tried

>>> root = build([7, 3, 2, 6, 9, None, 1, 5, 8, 1, 2])
>>> print(root)

        ______7
       /       \
    __3__       2
   /     \       \
  6       9       1
 / \     / \
5   8   1   2

But when I tried to add one more leaf to the node, I get an error.

>>> root = build([7, 3, 2, 6, 9, None, 1, 5, 8, 1, 2, 3])
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/binarytree/__init__.py", line 1651, in build
    .format(parent_index)
binarytree.exceptions.NodeNotFoundError: Parent node missing at index 5

It seems I cannot add the 3 to tree because theres a None node at index 5. I think the 3 should instead be added to the left child node of 1 (index 6)

Hello,

A quick question if that is the place to ask, is it possible to access the index of an individual node ?

I can't seem to find an easy way to do that.

Thanks !

Hey Joowani :),

I just created a build script of this package for archlinux (PKGBUILD). Maybe you can check if all is ok. If all is good, we can put this build option in README, that would be great for arch users :).

Cheers,
Joaquin

I'm not sure if the current way of calculating the is_bst property is correct. I thought for a bst, ALL nodes in left subtree should be less than parent, and ALL nodes in right subtree should be greater than (and possibly equal to if you want to allow duplicate keys) parent.

Seems like the current method only compares immediate left and right nodes to parent, so an example like this tree fails with current method:

    __ 2
 /       \
1         4
 \
  3

from binarytree import tree, convert, inspect
nodeList = [2, 1, 4, None, 3]
tree = convert(nodeList)
tree_props = inspect(tree)
assert(tree_props['is_bst'] == False)

Here's a brief list of functionality that I think would be really awesome to include in this library. Any feedback would be greatly appreciated. I'll get to these eventually if @joowani likes them and if no one gets to them first!

1. Parent node attribute functionality for each node. e.g. tree.right.right.left.parent
2. Level attribute functionality for each node. e.g. tree.right.right.level
3. A function for returning all nodes at each level. e.g. bt.get_level(tree, 6)
4. Index nodes by value or ID. e.g. tree["my node value"] or tree[6]. I'm thinking the second one makes more sense as a tree could potentially have the same value at different nodes.

I am a new user of binarytree and it's saving me some time in an algorithms class, so thank you!

Originally, I was scrolling up and down in the README.md a bunch, before I noticed the binarytree.readthedocs.io link on the right. The API Specification page was exactly what I was looking for.

Take a look at README of popular repos:

• https://github.com/PyCQA/isort
• https://github.com/python/mypy
• https://github.com/PyCQA/flake8

They all clearly have the docs hosting linked at the top of the README, which makes it very easy to discover the docs. I think isort does the best job of this.

I think it would be helpful for binarytree to do the same. Thank you for your consideration!