1

I just started learning data structures, I'm trying to learn binary tree implementation using python and found an article at a website. But I don't understand code on line 12 and 18, where it says self.left.insert(data) and self.right.insert(data). Can somebody explain me what is going on there? Thank you!

class Node:

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

def insert(self, data):
    """Compare node to parent node, decide to add new node as a left or a right node."""
    if self.data:  # if data is not none type
        if data < self.data:  # if new node is smaller than the parent node
            if self.left is None:  # if there is no left node
                self.left = Node(data)  # add as a left node
            else:  # ???
                self.left.insert(data)  # ???
        elif data > self.data:  # if new node is greater than the parent node
            if self.right is None:  # and if right node is empty
                self.right = Node(data)  # add as a right node
            else:  # ????
                self.right.insert(data)
    else:  # no root node, create it
        self.data = data
Infernalissss
  • 27
  • 4
  • 1
    `self.left` is a reference to another `Node` object, and it calls the `.insert()` method on that node. What part are you having difficulty understanding? – John Gordon Feb 27 '22 at 20:27
  • If you read the comments on code you'll see where I wrote question marks. In second if statement, I got that if left node is null I need to create a new node, but why do I need to write self.left.insert(data) if first else statement? I don't understand the logic there. Thanks. – Infernalissss Feb 27 '22 at 20:35
  • Do you know what [recursion](https://stackoverflow.com/questions/3021/what-is-recursion-and-when-should-i-use-it) is? – Sören Feb 27 '22 at 20:38
  • No I don't know what recursion is. – Infernalissss Feb 27 '22 at 20:46
  • See [Wikipedia](https://en.wikipedia.org/wiki/Binary_search_tree#Recursive_search), which also links to an article about recursion. I suggest you study the subject. – trincot Feb 27 '22 at 21:40
  • Basically, it will keep following down the tree until it gets to a point where it is right to insert the node. If there is no node there, than obviously it has reached the end. *If not*, it will continue down until it finds a spot to put it in. It continues down by calling itself again (recursion), and will repeat this until it has found the correct position to put itself. – Larry the Llama Feb 27 '22 at 23:21

0 Answers0