How does a binary search tree object print every element using recursion in Python?

Question

class Node:
    def __init__(self, value):
        self.value = value
        self.right = None
        self.left = None

class BinaryTree:
    def __init__(self):
        self.root = None

    def _append(self, value):

        self.root = self._appending(self.root, value)

    def _appending(self, node, value):
        if not node:
            node = Node(value)
        elif value > node.value:
            node.left = self._appending(node.left, value)
            print("==============",node.left.value)
        else:
            node.right = self._appending(node.right, value)
            print("--------------",node.right.value)
        return node

    def print_tree(self):
        if self.root is None:
            print("Binary tree is empty")
            return
        self._print_tree_recursive(self.root)

    def _print_tree_recursive(self, node):
        if node is None:
            return
        self._print_tree_recursive(node.right)
        print(node.value, end=" ")
        self._print_tree_recursive(node.left)


# Create an instance of BinaryTree
tree = BinaryTree()

# Add nodes to the binary tree
tree._append(1)
tree._append(2)
tree._append(-1)
tree._append(100)
tree._append(1)

# Print the binary tree
tree.print_tree()

i need to know how it print every elements. To be more clear

 def _print_tree_recursive(self, node):
        if node is None:
            return
        self._print_tree_recursive(node.right)
        print(node.value, end=" ")
        self._print_tree_recursive(node.left)

while it hits the line self._print_tree_recursive(node.right) it print -1 but how it manages to go back to the node which contains value 1 also -1's node.right and node.left is none. so how other values are printed

                                          1
                                         / \
                                       -1   2
                                             \
                                             100
                                               \
                                                1

when it reaches the node -1 how it can go back node 1.can you please explain it clearly as i am a beginner

Answer 1

Imagine you have this binary search tree:

                  D
              B       F
            A   C   E   G

An inorder traversal of the tree will return the nodes in order: A,B,C,D,E,F,G

The typical recursive algorithm is:

inorder(node)
    if (node == null)
        return
    inorder(node.left)
    print node.value
    inorder(node.right)
    return

One way of viewing things is in a hierarchy, with indentation at each recursive call. For example, below is the order of calls that occur after you make the initial call that passes the root (a reference to node D). At each indentation level, the return address and current node value are pushed onto the stack. And on return the most recently pushed values are popped from the stack:

inorder(D) 
    inorder(B)             // D.left
        inorder(A)         // B.left
            inorder(null)  // A.left
                return
            print A
            inorder(null)  // A.right
                return
            return
        print B
        inorder(C)         // B.right
            inorder(null)  // C.left
                return
            print C
            inorder(null)  // C.right
                return
        return
    print D
    inorder(F)             // D.right
        inorder(E)         // F.left
            inorder(null)  // E.left
                return
            print E
            inorder(null)  // E.right
                return
            return
        print F
        inorder(G)         // F.right
            inorder(null)  // G.left
                return
            print G
            inorder(null)  // G.right
                return
            return
         return
    return