Recursive insert method on Binary Tree reaches the correct node but it doesn't save data

Question

I'm trying to make a recursive insert method on a binary tree and while the recursive part of the function seems to do the job correctly (I tracked the code step by step with debug option) when time comes for data to be saved it just doesn't happen. Is it a reference mistake?

class TreeNode:
    def __init__(self, data=None, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

class BTree():
    def __init__(self, root=None):
        self.root = root

    def insert(self, data):

        def in_insert(node, data):
            if node is None:
                node = TreeNode(data)
            elif node.data == data:
                print(f'{node.data} already in here.')
            elif node.data > data:
                node = node.left
                in_insert(node, data)`
            else:
                node = node.right
                in_insert(node, data)

        if self.root is None:
            self.root = TreeNode(data)
        else:
            in_insert(self.root, data)

Yes, it is a reference mistake. Your line: node = TreeNode(data) does nothing. It simply reseats the parameter node and then throws it away. — quamrana
– quamrana, Commented Aug 16, 2024 at 10:11

Sachin Hosmani · Accepted Answer · 2024-08-16 11:22:32Z

You are expecting this line node = TreeNode(data) to insert into the tree. But it's simply creating a node within the scope of the function that isn't being referenced by any other node's left or right.

The fix would be

class BTree():
    def __init__(self, root=None):
        self.root = root

    def insert(self, data):
        def in_insert(node, data):
            if node is None:
                return TreeNode(data)
            elif node.data == data:
                print(f'{node.data} already in here.')
            elif node.data > data:
                node.left = in_insert(node.left, data)
            else:
                node.right = in_insert(node.right, data)
            return node

        if self.root is None:
            self.root = TreeNode(data)
        else:
            self.root = in_insert(self.root, data)

The changes are:

have in_insert return the node it just created if it did, or the subtree's head where the node got inserted
have the caller of in_insert set its left or right to the newly created node

But what is problematic with this is that it unnecessarily assigns the left or right references of all the nodes involved in the path to the added node. To optimise it, you could pass the parent node to the in_insert function to update the parent's left or right only at the point of insertion. Like so

class BTree():
    def __init__(self, root=None):
        self.root = root

    def insert(self, data):

        def in_insert(node, parent, is_left, data):
            if node is None:
                # We have found the point of insertion, time to create and insert
                if is_left:
                    parent.left = TreeNode(data)
                else:
                    parent.right = TreeNode(data)
            elif node.data == data:
                print(f'{node.data} already in here.')
            elif node.data > data:
                in_insert(node.left, node, True, data)
            else:
                in_insert(node.right, node, False, data)

        if self.root is None:
            self.root = TreeNode(data)
        else:
            in_insert(self.root, None, None, data)

Hanstjua · Accepted Answer · 2024-08-16 13:48:13Z

I think the previous answer has explained the problem with your code and provided a working solution. I just want to add on to the answer and say that you can represent the binary tree with only a single class (instead of two separate classes)

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

    def insert(self, data):
        if self.data is None:
            self.data = data
        elif self.data == data:
            print(f'{data} already in here.')
        elif self.data > data:
            if self.left is None:
                self.left = Node(data=data)
            else:
                self.left.insert(data)
        else:
            if self.right is None:
                self.right = Node(data=data)
            else:
                self.right.insert(data)

Collectives™ on Stack Overflow

Recursive insert method on Binary Tree reaches the correct node but it doesn't save data

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related