Bishalsarang / Recursion-Tree-Visualizer

A simple python package that helps to visualise any recursive function by adding a single line of code.
https://pypi.org/project/recursion-visualiser/
MIT License
111 stars 17 forks source link

Issue with visualizing DFS on a binary tree #28

Closed ManiAm closed 2 years ago

ManiAm commented 2 years ago

I am using this code snippet to perform DFS on a binary tree. The target value does not exist in the tree, so I am expecting to traverse all the nodes.

import os

os.environ["PATH"] += os.pathsep +  'C:/Program Files/Graphviz/bin/'
from visualiser.visualiser import Visualiser as vs

class tree_node():
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def build_tree():

    # leaf nodes
    l1 = tree_node(20)
    l2 = tree_node(21)
    l3 = tree_node(1)

    # internal nodes
    n1 = tree_node(3, l1, l2)
    n2 = tree_node(10, l3, None)

    # root node
    r = tree_node(5, n1, n2)

    return r

root = build_tree()

@vs(node_properties_kwargs={"shape":"record", "color":"#f57542", "style":"filled", "fillcolor":"grey"})
def dfs(node, target):
    if not node:
        return None
    if node.val == target:
        return node
    left = dfs(node.left, target)
    if left: # if target is found, then no need to search the right sub-tree
        return left
    return dfs(node.right, target)

match = dfs(root, 11)
if not match:
    print("not found")
else:
    print("found node: %s" % match)

# Save recursion tree to a file
vs.make_animation("dfs.gif", delay=2)

However, the DFS recursion tree that is generated does not look correct,

dfs

Am I missing something here?

Bishalsarang commented 2 years ago

Since you are using the custom class. You must implement the __repr__.

For simplicity, let's implement the repr to return the string representation of value

class tree_node():
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

    def __repr__(self):
        return str(self.val)

Then the tree looks as follows for dfs(root, 11)

image

Let's say we want dfs(root, 10), the tree looks sth like this

dfs dfs

ManiAm commented 2 years ago

Thanks!