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++) {
}
}
}
}
level order traversal in C | BFS in C
https://www.digitalocean.com/community/tutorials/level-order-traversal-in-a-binary-tree
Explain what is iterative pre-order traversal
- we are not going to use recursion here
- we will use stack DS
-
code for iterative pre-order traversal
explain what is iterative in-order traversal is
when to use iterative traversal techniques
iterative post-order traversal using 2 stack
iterative post order traversal using one stack
- traversal in one traversal, pre-order, in-order, post-order
- maximum depth in binary tree
Q. What is depth in BST
by which techniques we can find height / depth of BST
to get depth of BST we can use recursive or level order traversal
in this two techniques
Recursive and
Level order traversal
which one is better
in level order traversal we have to use queue Data Structure
Time com: O(N)
what will be time complexity for recursive method, for finding depth of BST
O (height)
- check for balanced binary tree
- diameter of Binary Tree
- Maximum path sum in Binary Tree
- check it two trees are Identical no Not
- Zig-Zag or Spiral Traversal in Binary Tree
- Boundary Traversal in Binary Tree
- Vertical Order Traversal of Binary Tree
- Top View of Binary Tree
- Bottom View of Binary Tree
- Right / Left View of Binary Tree
- check for symmetrical binary tree
- print root to node path in binary tree
- lowest common ancestor in binary tree
- maximum width of binary tree
- children sum property in binary tree
- print all the nodes at a distance of K in binary tree
- minimum time taken to BURN the binary tree from a Node
- count total nodes in COMPLETE Binary Tree
- requirements needed to construct a Unique Binary Tree
- construct a binary tree from pre-order and in-order traversal
- construct binary tree from post-order and in-order
- serialize and de-serialize binary tree
- Morris traversal - pre-order and in-order
- Flatten a Binary Tree to Linked List
- Introduction to Binary Search Tree
- Search in a Binary Search Tree
- ceil in a binary search tree
- floor in BST
- Insert a given node in BST
- delete node in BST
- k-th smallest/largest element in BST
- check if tree is a BST or BT, validate a BST
- LCA in BST
- construct a BST from a pre-order traversal
- in-order successor / predecessor in BST
- BST Iterator
- two sum in BST | check if there exists a pair with Sum K
- recover BST | correct BST with two nodes swapped
- largest BST in Binary Tree
Heap [syllabus]
what is heap?
what is heap sort
what are types of graph
Traversal of graph
