DSA Day-22

Hey Guys!! So, I hope you have tried the self evaluation test that I published earlier on the topics that we have covered till now: Arrays, Strings, Linked List, Hashing, Stacks, Queues.

If you’ve not tried it yet, I suggest that you try it once before moving on with the topic. Just learning blindly won’t get you to your destination, rather, practicing along with regular evaluations will give you an idea of how to improve yourself to ace the tests when you appear for the actual placements.

DSA (Revision + Self Evaluation)

Today, we’ll be moving to the next very important topic: TREES

This topic come out as quite confusing and many people just give up after trying for some time. But let me make it clear, you are not going to reach your dream company with this attitude. So, keep your spirits high and be obstinate about completing the topic.

Now, before we start with the concepts of trees, make sure that you’re well-versed with Recursion concepts. If you need some revision or sources, refer the following link where I have addressed this topic before:

DSA Day-13

Trees : Introduction

A Tree is a non-linear data structure where each node is connected to a number of nodes with the help of pointers or references.

Basic Tree Terminologies:

• Root: The root of a tree is the first node of the tree.
• Edge: An edge is a link connecting any two nodes in the tree.
• Siblings: The children nodes of same parents are called siblings of each other. That is, the nodes with same parents are called siblings.
• Leaf Node: A node is said to be the leaf node if it has no children.
• Height of a Tree: Height of a tree is defined as the total number of levels in the tree or the length of the path from the root node to the node present at the last level.

For very basic understanding of trees, you can refer to the following video:

Binary Trees : Concepts

A Tree is said to be a Binary Tree if all of its nodes have atmost 2 children. That is, all of its node can have either no child, 1 child or 2 child nodes.

Properties of Binary trees:

• The maximum number of nodes at level ‘l’ of a binary tree is (2l — 1). Level of root is 1.
• Maximum number of nodes in a binary tree of height ‘h’ is (2h — 1).
• In a Binary Tree with N nodes, the minimum possible height or the minimum number of levels is Log2(N+1).
• A Binary Tree with L leaves has at least (Log2L + 1) levels.
• In a Binary tree where every node has 0 or 2 children, number of leaf nodes is always one more than nodes with two children.

Binary Search Tree

Now Binary search trees are very important as most of the questions come from this. It’s not like we can ignore other topics, but binary trees and mainly binary search trees are very very important.

The concepts of binary search trees and binary trees should be on your finger tips if you are planning to sit for any online test involving data structures.

Not to overwhelm you with the forest of trees, we’ll stop here today and move on to the basic questions in the next segment of this series. But when we start solving, make sure that you understand these theoretical concepts first. Otherwise, it will pose as a major problem later when you attempt online MCQs or sit for interview because interviewers ask in depth questions based on each data strucutre.

If you are planning to sit for non- IT companies, I have started a short series on preparation for the same. The first segment is out, please go through it and stay tuned.

Placement Guide for Non- IT branches : Introduction

Visit us on instagram for more updates:

https://www.instagram.com/placementprep_aryagswm/