DSA - Trees Flashcards
What are trees in Data Structure?
Trees are non-linear DS
Where are Trees used?
Anywhere hierarchy is present. Like File and Folder structures.
What does Binary means in Binary Tree.
- binary is zero and ones, two elements
- binary in BT means, max to max only two nodes are present only
Why BT is Important?
- Lot of questions asked in interviews
What is Root in BT? What are childrens? What are Leaf Nodes? What is subtree?
- Root: node at top is root node
- Childrens: sub-nodes of any nodes are childres
- Leaf Nodes: end notes are root notes
- Sub tree:
What is Ancestors?
- parent of parent node
Types of Binary Tree
- full binary tree
- complete BT
- perfect BT
- balanced BT
5.
what is full binary tree
Either has 0 or 2 childrens
what is complete binary tree
- All levels are completely filled except the last level
- the last level has all nodes in left as possible
perfect BT
- all leaf nodes are at same level
balanced BT
- height of tree at max log(n)
- n is number of nodes
degenerate tree
How to represent BST in C
struct node{
int data;
struct node *left_child;
struct *right_child;
};
//function to create a node
struct node* new_node(int x) {
struct node *temp;
temp = malloc(sizeof(struct node));
temp -> data = x;
temp -> left_child = NULL;
temp -> right_child = NULL;
return temp;
}
// searching operation
struct node* search(struct node * root, int x) {
if (root == NULL || root -> data == x) //if root->data is x then the element is found
return root;
else if (x > root -> data) // x is greater, so we will search the right subtree
return search(root -> right_child, x);
else //x is smaller than the data, so we will search the left subtree
return search(root -> left_child, x);
}
// insertion
struct node* insert(struct node * root, int x) {
//searching for the place to insert
if (root == NULL)
return new_node(x);
else if (x > root -> data) // x is greater. Should be inserted to the right
root -> right_child = insert(root -> right_child, x);
else // x is smaller and should be inserted to left
root -> left_child = insert(root -> left_child, x);
return root;
}
Why traversal is required?
- To solve any problem on tree, we need to traverse it,
- Traversing is the starting point
What are Types of traversal in Tree
- DFS
- BFS
DFS is further categorized into three more categories
- in order
- pre order
- post order
What is in-order traversal
- it says go to the extreme left subtree, then apply the logic
Left => Root => Right
What is Pre-order
Root => Left => Right
What is Post Order traversal
Left => Right => Root
What is BFS Traversal
Breath First Traversal
- write nodes level by level
- from left to right
Implementation of Pre-order
- Root -> Left -> Right
Algorithm / Steps
- Code
// Here we print the preorder recursively
// 1. we start from root of the tree
// 2.
void preorder (struct node *root)
{
if (root != NULL)
{
printf (“%d “, root->data);
preorder (root->left);
preorder (root->right);
}
}
In order Traversal Code
void inorder(node){
if node == null
return;
inorder(node->left)
print(node)
inorder(node->right)
}
Post order traversal code
// this node we passed here, is root node
void postorder(node)
{
if node == null
return;
postorder(node->left)
postorder(node->right)
print(node)
// L Ri Root
}
Level Order Traversal of Binary Tree / BFS.
What DS we need?
Write code for it
C++ code
- Queue
// code for level order traversal
class solution{
public:
vector<vector<int>> levelOrder(TreeNode *root) {
if(root == NULL) return ans;</int>
queue<TreeNode*> q;
q.push(root);
while(!q.empty()) {
int size = q.size();
vector<int> level;</int>
for(int i=0; i < size ; i++) {
}
}
}
}
