# Lesson 2 - Common Data Structures in Python

Please visit the Lesson Page for more detailed info

Session Recordings:
English: https://youtu.be/HRhGDc6Qe9k
Hindi: https://youtu.be/9Dpk_mYsqJc

In this lesson, we explore the use-cases of binary search trees, and develop a step-by-step implementation from scratch, solving many common interview questions along the way.

### Notebooks used in this lesson:

Any has tried to implement “tree_to_tuple(node)”?

``````def tree_to_tuple(node):
if isinstance(node, TreeNode) and node.key != None and node.right != None and node.left != None:
node1 = tree_to_tuple(node.left)
node2 = tree_to_tuple(node.right)
node0 = (node1, node.key, node2)
#print(node0)
elif isinstance(node, TreeNode) and node.key != None and node.right != None and node.left == None:
node2 = tree_to_tuple(node.right)
node0 = (None, node.key, node2)
#print(node0)
elif isinstance(node, TreeNode) and node.key != None and node.right == None and node.left != None:
node1 = tree_to_tuple(node.left)
node0 = (node1, node.key, None)
#print(node0)
elif isinstance(node, TreeNode) and node.key != None and node.right == None and node.left == None:
node0 = node.key
#print(node0)
elif isinstance(node, TreeNode) and node.key == None :
node0 = None
#print(node0)
return node0
``````

This is my version. I am sure it could be better. Anyone has an idea how can we improve this?

4 Likes

Yes, I do have an idea
not my version though. It’s aakashns’s version (in the lesson2’s notebook itself). hehe

``````def to_tuple(self):
if self is None:
return None
if self.left is None and self.right is None:
return self.key
return TreeNode.to_tuple(self.left),  self.key, TreeNode.to_tuple(self.right)
``````
10 Likes

The last elif is not necessary and the following is my revised code:

``````def tree_to_tuple(node):
if node.right != None and node.left != None:
node1 = tree_to_tuple(node.left)
node2 = tree_to_tuple(node.right)
node0 = (node1, node.key, node2)
#print(node0)
elif node.right != None and node.left == None:
node2 = tree_to_tuple(node.right)
node0 = (None, node.key, node2)
#print(node0)
elif node.right == None and node.left != None:
node1 = tree_to_tuple(node.left)
node0 = (node1, node.key, None)
#print(node0)
elif node.right == None and node.left == None:
node0 = node.key
#print(node0)
return node0``````
3 Likes

Exercise : What is the time complexity of `__len__` ? Can you reduce it to O(1) . Hint: Modify the `BSTNode` class. (Lesson 2 Notebook)

How does modifying BSTNode class improve the time complexity of len function to O(1)?

4 Likes

Can you help me out with an example (i/p -> o/p)

So is there any way a linked list can be created in python without using the next() function?
I mean ideally, we have to point to the next node which initially we have always done using a pointer. And the next function is predefined to point to the next value in the iterable object.
I am curious as to how will I create a linked list from the basic definition of linked lists in python.

The code is listed at https://jovian.ai/aakashns/python-classes-and-linked-lists

1. Insert:

1. Inserting into an empty database of users
3. Inserting a user with a unique name which doesn’t matches with registered users and with a username that does not exist
4. Inserting a user, whose name matches with already existing users.
5. Inserting the user’s data without user’s emailid.
6. Inserting the user’s data without user’s name.
2. Find:

1. Finding a user in an empty database.
2. Finding a user, who didn’t even registered in the database.
3. Finding a user, who is already registered in the database.
4. Finding a user, whose name matches with other users.
5. Finding a user, whose email id is not available in the database.
6. Finding a user, whose name is not available in the database.
3. Update:

1. Updating name of the user, who has already registered in the database with all the data of the user.
2. Updating email of the user, who is already registered in the database with all the data of the user.
3. Updating info about the user, who is not registered in the database.
4. Updating name of the user, who is already registered in the database but the name of the user is not available.
5. Updating emailid of the user, who is already registered in the database but the emailid of the user is not
available.
4. List:

1. Listing an empty database.
2. Listing user profiles which aren’t registered in the database.
3. Listing user profiles which are registered in the database having all the data of the user.
4. Listing user profiles in which there are some users whose emailids are not available in the userdatabase.
5. Listing user profiles in which there are some users whose names are not available in the userdatabase.

ABOVE HERE, I AM PRESENTING THE EXAMPLE CASES FOR PROBLEM NO.1 IN LESSON_2, PLEASE HAVE A LOOK ON THIS AND PLEASE SUGGEST ANY OTHER CASES. ARE THE ABOVE CASES VALID ENOUGH FOR A GOOD FUNCTIONING DATA STRUCTURE.
@birajde, @aakashns and others please check it.

1 Like

Hello! Can anyone please explain why `i += 1` has been written in the code?
I cannot figure it out with the following example:

Lets say, we have the userdatabase of 4 users:
0: jahid
1: jeba
2: mehereen
3: munirul

and we want to insert `lamia`.

according to the code:
we iterate through the username until we find `mehereen` since `mehereen` > `lamia`
till now, `i = 2`
we break and increment `i` by 1, i.e., `i = 3`
and then we insert `lamia` at the `3rd` position which does not keep the list sorted.

Please explain how this code works.

TIA.

`break` means that you exit the loop without executing any further code in this loop. So the `i += 1` won’t execute.

1 Like

Opps… thanks.
I thought we are using a for loop here. and that was back in my mind.

Thanks a lot @Sebgolos

Even with `for` this wouldn’t execute `break` “breaks” any loop in the same way, no matter which one.

well, for `for loop` and deindenting `i += 1` satisfy my observation explained above :3

I did a complete mess understanding the code :3

Well I observed when repr() and str() are not used in the class and if we run the code cell containing the respective object of this class, the output is :

``````                                  **<__main__.User at 0x7fb5a8456a00>**
``````

Now if both of them are present in the class and if we run the code cell we get the output below:

So, when these two functions are included in the class, running the code cell containing the respective object, actually shows all the info of the user, whereas if those aren’t included output of code cell containing the respective object exhibit that the object is of corresponding class.

So this shows that these two functions helps to obtain all the info which was stored and also exhibits the respective class of the object, whereas if they aren’t present, running the code cell containing only object the output just shows the respective class of that object.

when you break, the rest of the statements in the loop are no longer executed. So i is not incremented.

2 Likes

Thank you @aakashns. I got the point!

An additional point on this code snippet:
While I was looking at this code snippet I got confused when I saw `self.users.insert(i,user)`, It took me a while to realize that `.insert(i,user)` is the in-built insert() method of the list defined inside the init method.

Note: This clarification post is intended for beginners who should not think that above method call was a recursive function call.

2 Likes

My assignment 2 is checked but but not assignment 1 which I have submitted more than a week ago. I just wanted to draw your attention. I understand you need time to check all assignment but just wanted to draw your attention.