DSA - Trees

Question 1

What are trees in Data Structure?

Answer 1

Trees are non-linear DS

Question 2

Where are Trees used?

Answer 2

Anywhere hierarchy is present. Like File and Folder structures.

Question 3

What does Binary means in Binary Tree.

Answer 3

• binary is zero and ones, two elements
• binary in BT means, max to max only two nodes are present only

Question 4

Why BT is Important?

Answer 4

• Lot of questions asked in interviews

Question 5

What is Root in BT? What are childrens? What are Leaf Nodes? What is subtree?

Answer 5

• Root: node at top is root node
• Childrens: sub-nodes of any nodes are childres
• Leaf Nodes: end notes are root notes
• Sub tree:

Question 6

What is Ancestors?

Answer 6

• parent of parent node

Question 7

Types of Binary Tree

Answer 7

1. full binary tree
2. complete BT
3. perfect BT
4. balanced BT
   5.

Question 8

what is full binary tree

Answer 8

Either has 0 or 2 childrens

Question 9

what is complete binary tree

Answer 9

1. All levels are completely filled except the last level
2. the last level has all nodes in left as possible

Question 10

perfect BT

Answer 10

• all leaf nodes are at same level

Question 11

balanced BT

Answer 11

• height of tree at max log(n)
• n is number of nodes

Question 12

degenerate tree

Question 13

How to represent BST in C

Answer 13

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;
}

Question 14

Why traversal is required?

Answer 14

• To solve any problem on tree, we need to traverse it,
• Traversing is the starting point

Question 15

What are Types of traversal in Tree

Answer 15

1. DFS
2. BFS

DFS is further categorized into three more categories
- in order
- pre order
- post order

Question 16

What is in-order traversal

Answer 16

• it says go to the extreme left subtree, then apply the logic
  Left => Root => Right

Question 17

What is Pre-order

Answer 17

Root => Left => Right

Question 18

What is Post Order traversal

Answer 18

Left => Right => Root

Question 19

What is BFS Traversal

Answer 19

Breath First Traversal
- write nodes level by level
- from left to right

Question 21

Implementation of Pre-order

Answer 21

• 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);
}
}

Question 22

In order Traversal Code

Answer 22

void inorder(node){

if node == null
return;

inorder(node->left)
print(node)
inorder(node->right)

}

Question 23

Post order traversal code

Answer 23

// 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
}

Question 24

Level Order Traversal of Binary Tree / BFS.
What DS we need?
Write code for it

Answer 24

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++) {

}
}
}
}

Question 25

level order traversal in C | BFS in C

Answer 25

https://www.digitalocean.com/community/tutorials/level-order-traversal-in-a-binary-tree

Question 26

Explain what is iterative pre-order traversal

Answer 26

- we are not going to use recursion here - we will use stack DS -

Question 27

code for iterative pre-order traversal

Question 28

explain what is iterative in-order traversal is

Question 29

when to use iterative traversal techniques

Question 30

iterative post-order traversal using 2 stack

Question 31

iterative post order traversal using one stack

Question 32

13. traversal in one traversal, pre-order, in-order, post-order

Question 33

14. maximum depth in binary tree Q. What is depth in BST

Question 34

by which techniques we can find height / depth of BST

Answer 34

to get depth of BST we can use recursive or level order traversal

Question 35

in this two techniques Recursive and Level order traversal which one is better

Answer 35

in level order traversal we have to use queue Data Structure Time com: O(N)

Question 36

what will be time complexity for recursive method, for finding depth of BST

Answer 36

O (height)

Question 38

15. check for balanced binary tree

Question 39

16. diameter of Binary Tree

Question 40

17. Maximum path sum in Binary Tree

Question 41

18. check it two trees are Identical no Not

Question 42

19. Zig-Zag or Spiral Traversal in Binary Tree

Question 43

20. Boundary Traversal in Binary Tree

Question 44

21. Vertical Order Traversal of Binary Tree

Question 45

22. Top View of Binary Tree

Question 46

23. Bottom View of Binary Tree

Question 47

24. Right / Left View of Binary Tree

Question 48

25. check for symmetrical binary tree

Question 49

26. print root to node path in binary tree

Question 50

27. lowest common ancestor in binary tree

Question 51

28. maximum width of binary tree

Question 52

29. children sum property in binary tree

Question 53

30. print all the nodes at a distance of K in binary tree

Question 54

31. minimum time taken to BURN the binary tree from a Node

Question 55

32. count total nodes in COMPLETE Binary Tree

Question 56

33. requirements needed to construct a Unique Binary Tree

Question 57

34. construct a binary tree from pre-order and in-order traversal

Question 58

35. construct binary tree from post-order and in-order

Question 59

36. serialize and de-serialize binary tree

Question 60

37. Morris traversal - pre-order and in-order

Question 61

38. Flatten a Binary Tree to Linked List

Question 62

39. Introduction to Binary Search Tree

Question 63

40. Search in a Binary Search Tree

Question 64

41. ceil in a binary search tree

Question 65

42. floor in BST

Question 66

43. Insert a given node in BST

Question 67

44. delete node in BST

Question 68

45. k-th smallest/largest element in BST

Question 69

46. check if tree is a BST or BT, validate a BST

Question 70

47. LCA in BST

Question 71

48. construct a BST from a pre-order traversal

Question 72

49. in-order successor / predecessor in BST

Question 73

50. BST Iterator

Question 74

51. two sum in BST | check if there exists a pair with Sum K

Question 75

52. recover BST | correct BST with two nodes swapped

Question 76

53. largest BST in Binary Tree

Question 77

Heap [syllabus] what is heap?

Question 78

what is heap sort

Question 79

what are types of graph

Question 80

Traversal of graph