What is wrong with the print_tree method in my Binary Search Tree Class?

Question

Below is my implementation of a BST in python:


class Node:
    def __init__(self,value):
        self.value = value
        self.left = None
        self.right = None
        
class BinarySearchTree:
    def __init__(self):
        self.root = None
    
    def insert(self,value):
        new_node = Node(value)
        if self.root is None:
            self.root = new_node
            return True
        temp = self.root
        while (True): 
            if new_node.value == temp.value:
                return False
            if new_node.value < temp.value: #left
                if temp.left is None:
                    temp.left = new_node
                    return True
                temp = temp.left
            else:                           #right
                if temp.right is None:
                    temp.right = new_node
                    return True
                temp =temp.right
                
    def contains(self,value):
        temp = self.root
        while (temp is not None):
            if value < temp.value:
                temp = temp.left
            elif value > temp.value:
                temp = temp.right
            else:
                return True
        return False
    
    def print_tree(self, level=0):
        if self.root is not None:
            self.print_tree(self.root.right, level + 1)
            print("   " * level + "->", self.root.value)
            self.print_tree(self.root.left.value, level + 1)

To run it I use these commands:

    my_tree = BinarySearchTree()
    my_tree.insert(2)
    my_tree.insert(1)
    my_tree.insert(3)

But for some reason I get this error when I run 'my_tree.print_tree()'

enter image description here

Any suggestions are welcome.

I was expecting this output to pop out:
    -> 3
-> 2
    -> 1

I'm guessing it most likely has something to do with the recursive call in the print_tree method.

[Please don't post screenshots of text](https://meta.stackoverflow.com/a/285557/354577). They can't be searched or copied, or even consumed by users of adaptive technologies like screen readers. Instead, paste the code as text directly into your question, then select it and click the code block button. — ChrisGPT was on strike, Mar 12 '23 at 23:11
I would suggest looking at this answer for inspiration: https://stackoverflow.com/a/49844237/5237560 — Alain T., Mar 12 '23 at 23:42

score 1 · Answer 1 · edited Mar 13 '23 at 19:57

1

Your print_tree has only one argument, "level". In python classes, self is not counted as argument, you have to pass it as a argument in the function definition if you use any class attributes (variables). However, in recursive call inside the print_tree you're passing two args, "current root" and "level". following is the correct version of print_tree. whenever you call it, you have to pass the root of the tree and level (level is optional tho)

    def print_tree(self,current, level=0):
                if current is not None:
                    self.print_tree(current.right, level + 1)
                    print("   " * level + "->", cuurent.value)
                    self.print_tree(current.left, level + 1)

EDITED (print_tree without any passing any parameters):

def helper_print_tree(self, current, level):
    if current is not None:
        self.helper_print_tree(current.right, level + 1)
        print("   " * level + "->", current.value)
        self.helper_print_tree(current.left, level + 1)

def print_tree(self):
    self.helper_print_tree(self.root,0 )

edited Mar 13 '23 at 19:57

Ryan Haining

35,360
15
114
174

answered Mar 12 '23 at 23:33

Qasim

11
2

I'd also suggest changing the name from `root` to `current` to distinguish it from the tree's `root` node. – Ryan Haining Mar 12 '23 at 23:39
OP wants to be able to call `bst.print_tree()` though, so what you really want here is for there to be a `def print_tree(self):` function that kicks off the recursion like `self.print_tree_impl(self.root, 0)` – Ryan Haining Mar 12 '23 at 23:40
Hey Qasim, thanks for your answer. Is there a way to create this function without having to input any parameters to it? Meaning the function should just use self as a parameter and nothing else. – Vish P Mar 13 '23 at 02:31
@VishP, hey sure. It depends on you how you made your classes. In the code above, you made separate classes for node and bst. Therefore, you can make two member functions (functions which are member of a class). Please refer to the EDITED code above, i made two member functions print_tree() and helper_print_tree(). print_tree() will call the helper_print_tree() by passing all the required parameters. It is helper_print_tree() that'll print the entire tree. print_tree() is just there so we can call print function without passing any parameters to it. I hope it clear things – Qasim Mar 13 '23 at 19:44
@RyanHaining, changed the name, thanks for the suggestion!! – Qasim Mar 13 '23 at 19:44

score 0 · Answer 2 · answered Mar 13 '23 at 19:55

The problem is that self.print_tree(self.root.right, level + 1) will want to pass self as first argument, then self.root.right as second argument, and finally level + 1 as third argument. But the method only expects 2 (including self).

You can fix this in several ways.

It is however preferable not to have a method that calls print. Instead, define a function that returns the string (that you can print or write to a file, or send to another application, ...etc). For instance, you could implement __repr__:

    def __repr__(self):
        def subtree(root, indent):
            if not root:
                return ""
            return ( subtree(root.right, "   " + indent)
                   + f"{indent}-> {root.value}\n"
                   + subtree(root.left, "   " + indent) )

        return subtree(self.root, "")

Now you can do:

print(my_tree)

What is wrong with the print_tree method in my Binary Search Tree Class?

2 Answers2