Answer Detail: prove that no of leaf nodes in any binaryy tree is one more than the no of nodes with degree 2

GeekInterview.com > Placement Papers > Adobe > Placement Papers

Print |

Question: HI Everybody,
I attended Adobe test on 16-07-2006. it was cool test. The test was 3 hours. I am sending u Questions Asked on Engineering and C. Merit-Trac conducted the test. The test was for both Developmnt & testing Domain. I attended for Dev posn.

ADOBE Written Test

1) Wap to reverse a linked list and sort the same.

2) Given two integers A & B. Determine how many bits required to convert
A to B. Write a function int BitSwapReqd(int A, int B);

3) Write an algorithm to insert a node into sorted linked list.After inserting,
the list must be sorted.

4) Without using /,% and * operators. write a function to divide a number by 3.
itoa() function is available.

5) Wap to swap two integer pointers.

6)Write a funcn int round(float x) to round off a floating point num to int.

7) write an ALP to find sum of First n natural numbers using the following Instructions

LDA num ; load Accumulator with num
DCR R ; decrement Register R
INR R ; increment Register R
MOV x,y ; move the contents of register y into register x
JZ label ; jump to label if A=0
DJNZ label; Decrement & Jump if A <> 0
you can use B & C registers in addition to A register

8) Find the n th node in a Singly Linked list starting from the End in a Single Pass.

9)prove that a tree is BST.what is height of a tree?

10) Given A,B & C Boolean polynomials.Prove That (A+BC)=(A+B)(A+C)

November 11, 2006 12:18:21	#3
rsk	Member Since: Visitor Total Comments: N/A
prove that no of leaf nodes in any binaryy tree is one more than the no of nodes with degree 2
Total no of nodes of a binary tree of depth d = 1 + 2 + 2^2 + 2^3+ .......+2^d No of leaf nodes = 2^d No of non leaf nodes = root nodes + elements upto d-1th level = 1+ (2(1-2^(d-1))/(1-2)) #gp sum of elements =(1-2+2-2^d)/(1-2) =(1-2^d)/-1 =2^d-1 =no of leave nodes -1 so no of leve nodes = no of non_leaf nodes +1 i.e no of leaf nodes in any binaryy tree is one more than the no of nodes with degree 2

Back To Question