Lesson 2 - Common Data Structures in Python

Please visit the Lesson Page for more detailed info :point_up:

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

:zap: 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:

:question: Asking/Answering Questions :
Reply to this thread to ask questions. Before asking, scroll through the thread and check if your question (or a similar one) is already present. If yes, just like it. We will give priority to the questions with the most likes. The rest will be answered by our mentors or the community. If you see a question you know the answer to, please post your answer as a reply to that question. Let’s help each other learn!

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 :raised_hand:
:smile: 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)
8 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)?

3 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
    2. Trying to insert a user with username that already exists
    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.

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 :smiling_face_with_three_hearts:

Even with for this wouldn’t execute :stuck_out_tongue: 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:
User(username=‘jane’, name=‘Jane Doe’, email=‘jane@doe.com’)

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! :smiling_face_with_three_hearts:

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.

1 Like

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.