Understanding binary search tree insertion using Python

Question

I'm trying to understand following binary search tree node insertion implementation in Python. I have placed a few print statements within the insert function. I could understand the first two prints generated by two insert calls but I couldn't understand third print generated seems before 3rd insert call. The implementation with debug prints looks as follows:

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


def insert(root, node):
    if root is None:
        root = node
        return root
    if node.value < root.value:
        root.left = insert(root.left, node)
        print("left: " + str(root.left.value))
    if node.value > root.value:
        root.right = insert(root.right, node)
        print("right: " + str(root.right.value))
    return root


root = Node(50)

insert(root, Node(10))
insert(root, Node(2))
insert(root, Node(80))
insert(root, Node(15))
insert(root, Node(60))
insert(root, Node(90))

The code prints:

left: 10
left: 2
left: 10
right: 80
right: 15
left: 10
left: 60

right: 80
right: 90
right: 80

My understanding so far:

insert(root, Node(10))

(i) __init__ with value = 10 called. Since root is already set to 50, program gets inside second if condition with 10<50.

(ii) recursive insert function is called with root.left as None and node value as 10. Since root.left is None now, program gets in to first if condition and root gets value 10. This finishes the recursive call and program executes next statement which is print("left: " + str(root.left.value)) this prints 10. Program evaluates third if condition as false as expected and finishes the function call for the insertion of 10.
insert(root, Node(2))

(i) __init__ with value=2 called. Program gets inside second if condition with 2<50.

(ii) recursive insert function is called with root.left as 10 and node value as 2. Program again gets in to second if condition with 2<10.

(iii) recursive insert function is called again with root.left as None and value as 2. Now program gets in to first if condition and root gets value 2. This finishes the recursive repeat calls and program executes next print statement print("left: " + str(root.left.value)) which prints 2.

(iv) Now as expected program evaluates third if condition as false and successfully calls return.
But, before starting insert(root, Node(80)), it again goes back to print statement in second if condition and prints a 10.
I did not get this, that why after finishing (or is it not?) the function call it is going back to the print statement again?

Not sure if you know this, but there is a site called pythontutor.com, go there and paste your code and see a step by step visualization of what's happening. — ababuji
– ababuji, Commented Jul 21, 2018 at 23:01

B. Almeida · Accepted Answer · 2018-07-21 23:37:48Z

2

When node 2 is being inserted, it goes in the second if statement two times, as you've said:

insert(root, Node(2)) -> root being Node 50
insert(root, Node(2)) -> root being Node 10

So, when the recursive step ends, two print statements will run, but in the opposite order. This means that the first print will show Node 10's left (Node 2 that was inserted) and the second print will show Node 50's left (Node 10)

You can visualize the code above as a stack, so everything needs to be executed before the algorithm finishes and what is in the top will be executed first.

answered Jul 21, 2018 at 23:37

B. Almeida

3851 silver badge13 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Nafeez Quraishi · Accepted Answer · 2018-10-19 15:09:30Z

I tried a few experiments and based on the outcomes, following is an answer:

Additional prints are getting executed for the nodes which are injected 2 or more level deeper as the insert function's return root is going via intermediate nodes to the root. Posting the code with additional debug prints for tracking ids of root objects and time stamp of print executions.

Code:

import time


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


def insert(root, node):
    if root is None:
        root = node
        return root
    if node.value < root.value:
        root.left = insert(root.left, node)
        print("left: " + str(root.left.value) + "  " + str(time.clock()))
    if node.value > root.value:
        root.right = insert(root.right, node)
        print("right: " + str(root.right.value) + "  " + str(time.clock()))
    print(id(root))
    return root


root = Node(50)
print("root node id: " + str(id(root)))

insert(root, Node(10))
insert(root, Node(2))
insert(root, Node(80))
insert(root, Node(15))
insert(root, Node(60))
insert(root, Node(90))

Program output with inline comments:

root node 50 was assigned object id 50359600

 root node id: 50359600

First node 10 inserted

left: 10  3.77580764525532e-07

With the return root call insert function returns root 50 residing at 50359600

50359600

Second node 2 inserted

left: 2  3.398226880729788e-05

With the return root call insert function returns to the 50359600 but via 50360272 (id of 2's immediate root 10) and prints 10 before returning root 50 @ 50359600

50360272
left: 10  4.8330337859268096e-05
50359600

80 is a right side node immediately after 50 on the right hand side, so return root directly reaches 50@50359600 after injecting 80.

right: 80  6.305598767576385e-05
50359600

Similar to node 2 in earlier execution, after inserting 15 insert function has to return to 50 with return root call via 10.

right: 15  7.702647596320853e-05
50360272
left: 10  8.986422195707663e-05
50359600

Likewise....

left: 60  0.00010345712947999577
50360304
right: 80  0.0001155397139448128
50359600

right: 90  0.00012837745993868089
50360304
right: 80  0.00014008246363897238
50359600

Collectives™ on Stack Overflow

Understanding binary search tree insertion using Python

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