1) A Binary Tree can have
- Can have 2 children
- Can have 1 children
- Can have 0 children
Explanation: Binary tree can have at most 2 children.
2) Height of Height of a binary tree is
- MAX( Height of left Subtree, Height of right subtree)+1
- MAX( Height of left Subtree, Height of right subtree)
- MAX( Height of left Subtree, Height of right subtree)-1
3) Postfix expression for (A+B) *(C+D) is
- A B C * + D +
- A B + C D + *
In postfix form two operands come together then operator. For example, in A+B, A and B are two operands and + is one operator and A+B is in infix form. Hence, in postfix of A+B will be AB+.
Let’s consider the question above
(A+B) *(C+D)//this expression is in infix form
First get A and B operand together then operator +. Similarly, for C and D
(AB+) * (CD+)
now consider AB+ and CD+ as two operands. Take them together then * operator.
(AB+) (CD+) *
So, AB+CD+* is the postfix expression of (A+B) *(C+D) infix expression.
4) True statements about AVL tree are
- It is a binary search tree.
- Left node and right node differs in height by at most 1 unit
- Worst case time complexity is O(log2n)
- Worst case time complexity is O(n)
Answer: 1, 2 and 3
A side note: AVL tree is a self balancing binary tree and named after inventors Adelson-Velsky and Landis …wikipedia..
5)Match the following for binary tree traversal
|(1) Pre Order||(A)Left Right Root|
|(2) In Order||(B)Left Root Right|
|(3) Post Order||(C)Root Left Right|
- 1 → A, 2 → B, 3 → C
- 1 → C, 2 → B, 3 → A
- 1 → A, 2 → C, 3 → B
- 1 → B, 2 → A, 3 → C