Problems based on Binary Tree

1.A strictly binary tree contains 10 leaves(nodes dont have children). find the total number of nodes in the tree?

Solution

Total number of nodes=19
A strictly binary tree with n leaves always contains 2n-1 nodes.so the tree has 2*10-1 ie 19 nodes

2.A binary tree has 20 nodes. Then how many null branches have the tree?

Solution

Answer=21 null branches
If the tree has 3 nodes then it has 4 null branches.ie 3+1. If the tree has 5 nodes then it has 6 null branches.ie5+1. In general a binary tree with n nodes has exactly n+1 null nodes. So 20 nodes has 21 null branches.

3.In the given binary tree below, in which location the node 4 is stored in an array?

Solution:The node 4 is stored at location 6.
The nodes are stored in the array in the order of root first then left child of root,right child of root, then left child of child1,right child of child1,then left child of child2 ,right child of child 2 and so on.

Here LCn means left child of node n and RCn means right child of node n.
In array the index starts from 0. so the node 4 is at location 6. but the index value is 5.

4.Comparing to Incomplete Binary Tree,Complete Binary Tree and Full Binary Tree,Which tree is efficient considering space and time complexities?
Solution

Complete Binary Tree
Full binary tree loses its nature when operationas of insertions and deletions are done. For Incomplete Binary trees extra storage is required and overhead of NULL node checking takes place. So complete binary tree is the better one since the property of complete binary tree is maintained even after operations like additions and deletions are done on it.

5.Draw a Binary Tree for the expression A*B-(C+D)*(P/Q)?
Solution

Problems based on Tree

Problem 1:
List out some of the application of tree data structure?
Answer

1. Manipulation of Arithmetic expression
2. Symbol Table construction
3. Syntax analysis

Problem 2
In a tree construction which is the suitable efficient data structures?
(a) Array
(b) Linked list
(c) Stack
(d) Queue
(e) None

Answer:
(b) Linked list

Problem 3 
How many different trees are possible with 10 nodes?
Answer
In general If there are n nodes then there exist 2ⁿ-n different trees
here n=10
so 2¹⁰-10==>1024-10=1014
So there are 1014 different possible trees available.

Problem 4
How many differnt trees are possible with 3 nodes and show the possible trees?
Answer
here n=3
2ⁿ-n=2³-3=8-3=5
So a tree with 3 nodes have the maximum combination of 5 different trees.
The different possible trees are shown below

Problem 5
Consider the tree shown in figure

1. Which node is the root node?
2. Which nodes are Leaves?
3. What is the depth of the tree?
4. What is the degree of the tree?
5. For each node in the tree

          (A) Name the parent node
          (B) List the children
          (C) List the siblings
          (D) Compute the depth
          (E) Compute the height

Answer

Problems based on Queue

Problem 1:
Suppose that a client performs an intermixed sequence of enqueue and dequeue operations in a queue.The enqueue operations put the integers o through 9 in order on to the queue, the dequeue operations print out the return value.Which of the following sequences could not occur?

1. 0 1 2 3 4 5 6 7 8 9
2. 4 6 8 7 5 3 2 9 0 1
3. 2 5 6 7 4 8 9 3 1 0
4. 4 3 2 1 0 5 6 7 8 9

Problem 2
In a queue, if rear=front then what will be the queue
a) Queue is empty
b) Queue is full
c) Queue has only one element
d) none of the above

Problem 3
In a queue,if rear=0,front=0 then what will be the queue
a) Queue is empty
b) Queue is full
c) Queue has only one element
d) none of the above

Problem 4
In a queue,if rear=0,front=1 then what will be the queue
a) Queue is empty
b) Queue is full
c) Queue has only one element
d) Queue is circular

Problem 5
In a queue,if rear=-1,front=-1 then what will be the queue
a) Queue is empty
b) Queue is full
c) Queue has only one element
d) none of the above

Problem 6
In a queue,if rear=max-1,front=0 then what will be the queue
a) Queue is empty
b) Queue is full
c) Queue has only one element
d) none of the above

Problems based on Expression Evaluation

Problem 1:
Give postfix form of the following expression

1. A*(B+(C+D)*(E+F)/G)*H 
2. A+((B+C)*(D+E)*F)/G
3. A*(B+D)/E-F-(G+H/K)
4. ((A-B)*(D/E))/(F*G*H) 

Problem 2:
Evaluate the following postfix expression using a stack and show the contents of stack after each step

1. 50 40 +18 14-4*+
2. 100 40 8+20 10 -+*
3. 5 6 9 +80 5*-/
4. 120 45+20 10-15+*
5. 20 45+20 10-15+* 

Problem 3:
Simplify the following infix expressions using operator precedence rules

1.  8-2*3-1
2. 12/(6-2)
3. (4+3)*(8-5)

Solution:
(1) A=8-2*3-1
      * has higher precedence than -. so 2*3 is executed first
      A=8-6-1.both are -.so evaluate from left to right
      A=2-1=1
       A=1

(2)B=12/(6-2)
    operation in parentheses are done first.so 6-2=4
    B=12/4=3
      B=3
(3)C=(4+3)*(8-5)
     operation in parentheses done first
      C=7*(8-5)
      C=7*3
      C=21

Problem 4
Are the following two infix expressions equivalent?

1. A+B*C
2. (A+B)*C 

Solution:
      The two infix expressions are different.The multiplication is performed first in the first expression while the addition is performed first in the second expression.

Problems Based On Stack

Problem 1: What would be the state of a stack after the following operations
create stack
push A on to stack 
push F on to stack
push X on to stack
pop item from stack
push B on to stack
pop item from stack
pop item from stack. 
Solution: 
                                                          Stack 

create stack                          -->      Empty stack
push A on to stack                -->      A
push F on to stack                 -->     FA
push X on to stack                -->      XFA
pop item from stack              -->      FA
push B on to stack                -->      BFA 
pop item from stack              -->      FA
pop item from stack.             -->      A

 Finally the stack contains A only

Problem 2: Show the state of the stack and the value of each variable after execution of
each of the following statements:
A = 5 B = 3 C = 7
(a) create stack
push A onto stack
push C*C onto stack
pop item from stack and store in B
push B+A onto stack
pop item from stack and store in A
pop item from stack and store in B
(b) create stack
push B onto stack
push C onto stack
push A onto stack
A = B * C
push A+C onto stack
pop item from stack and store in A
pop item from stack and store in B
pop item from stack and store in C

 Solution for a:
                                                        operation               Stack    
create stack                                                                  Empty stack
 push A onto stack                             Push 5                5    
 push C*C onto stack                        push 7*7            49 5
 pop item from stack and store in B    pop 49& B=49   5 
push B+A onto stack                         push 54               54 5
 pop item from stack and store in A    pop 54& A=54   5
 pop item from stack and store in B    pop 5 & B=5       Empty stack

Now A=54,B=5 and C=7 

Solution for b:
                                                                Stack
create stack                                                   Empty stack   
push B onto stack                                         3 
push C onto stack                                         7 3
 push A onto stack                                        5 7 3
 A = B * C-->A=21
 push A+C onto stack -->21+7->28            28 5 7 3
 pop item from stack and store in A->A=28  5 7 3
 pop item from stack and store in B->B=5     7 3
 pop item from stack and store in C->C=7     3

Now A=28,B=5 and C=7 

Problem 3:A function f defined on stacks of integers satisfies the following properties. f(∅)= 0 and f(push(S,i))=max⁡(f(S),0)+ i for all stacks S and integers i.
If a stack S contains the integers 2, -3, 2, -1, 2 in order from bottom to top, what is f(S)?
(a) 6
(b) 4
(c) 3
(d) 2


Solution:
Initially stack is empty. S->{}. so f(S)=0
Push 2 in to stack S.
f(push(S,2)=f(push({},2)=max(f(S),0)+2=max(0,0)+2=0+2=2
now S->{2} and f(S)=2
push -3 in to Stack S
f(push({2},-3))=max(f(S),0)+(-3)=max(2,0)+(-3)=2-3=-1
now S->{2,-3} and f(s)=-1
push 2 in to stack S
f(push({2,-3},2)=max(-1,0)+2=0+2=2
now S->{2,-3,2} and f(S)=2
push -1 in to stack S
f(push({2,-3,2},-1))=max(2,0)+(-1)=2-1=1
now S->{2,-3,2,-1} and f(S)=1
push 2 in to stack S
f(push({2,-3,2,-1},2))=max(1,0)+2=1+2=3
now S->{2,-3,2,-1,2} and f(S)=3

so finally f(S)=3

Problem 4:Suppose that a client performs an intermixed sequence of (stack) push and pop operations. The push operations put the integers 0 through 9 in order on to the stack; the pop operations print out the return value. Which of the following sequences could not occur?
(a) 4 3 2 1 0 9 8 7 6 5
(b) 4 6 8 7 5 3 2 9 0 1
(c) 2 5 6 7 4 8 9 3 1 0
(d) 4 3 2 1 0 5 6 7 8 9
(e) 1 2 3 4 5 6 9 8 7 0
(f) 0 4 6 5 3 8 1 7 2 9
(g) 1 4 7 9 8 6 5 3 0 2
(h) 2 1 4 3 6 5 8 7 9 0 
Solution
Sequence b,f,g couldn't occur 


Problem 5:
 Let S be a stack of size n >= 1. Starting with the empty stack, suppose we push the first n natural numbers in sequence, and then perform n pop operations. Assume that Push and Pop operation take X seconds each, and Y seconds elapse between the end of one such stack operation and the start of the next operation. For m >= 1, define the stack-life of m as the time elapsed from the end of Push(m) to the start of the pop operation that removes m from S. The average stack-life of an element of this stack is (GATE CS 2003)
a) n(X+ Y)
b) 3Y + 2X
c) n(X + Y)-X
d) Y + 2X

Solution
Answer is n(X+Y)-X 

Problem 6:
The following sequence of operation is performed on a stack push(1),push(2),pop,push(1),push(2),pop,pop,pop,push(2),pop. The sequences of popped out values are

1. 2,2,1,2,1
2. 2,2,1,1,2
3. 2,1,2,2,1
4. 2,1,2,2,2

Solution
 Answer is (2) 2,2,1,1,2