DS

Question 1

What is The maximum number of nodes at level ‘l’ of a binary tree?

Answer 1

2^(l-1).

level or root = 1

Question 2

What is the maximum number of nodes in a binary tree of height ‘h’?

Answer 2

2^(h) – 1.

height of a tree is maximum number of nodes on root to leaf path.

Question 3

In a Binary Tree with N nodes, what is the minimum possible height or minimum number of levels?

Answer 3

Log2(N+1)

Question 4

What is a full binary tree?

Answer 4

A Binary Tree is full if every node has 0 or 2 children.

Question 5

What is a complete binary tree?

Answer 5

A Binary Tree is complete Binary Tree if all levels are completely filled except possibly the last level and the last level has all keys as left as possible

Question 6

What is a perfect binary tree?

Answer 6

A Binary tree is Perfect Binary Tree in which all internal nodes have two children and all leaves are at the same level.

Question 7

What is a balanced binary tree

Answer 7

A binary tree is balanced if the height of the tree is O(Log n)

AVL tree maintains O(Log n) height by making sure that the difference between heights of left and right subtrees is 1. Red-Black trees maintain O(Log n) height by making sure that the number of Black nodes on every root to leaf paths are same and there are no adjacent red nodes.

Question 8

What is a degenerate tree?

Answer 8

A degenerate or pathological tree is a tree where every internal node has one child.

Question 9

When DFS vs BFS?

Answer 9

Depth First Traversals are typically recursive and recursive code requires function call overheads.

The most important points is, BFS starts visiting nodes from root while DFS starts visiting nodes from leaves. So if our problem is to search something that is more likely to closer to root, we would prefer BFS. And if the target node is close to a leaf, we would prefer DFS.

Question 10

When to use trees?

Answer 10

1. Storing hierarchical data
2. an search for a given key in moderate time (quicker than Linked List and slower than arrays)
3. can insert/delete keys in moderate time (quicker than Arrays and slower than Unordered Linked Lists).
4. Like Linked Lists and unlike Arrays, Pointer implementation of trees don’t have an upper limit on number of nodes as nodes are linked using pointers.