Suppose a binary tree is implemented as a linked structure in which each node contains both a left and right child pointer, either of which can be null or point to a node. Which of the following statements is false for this structure?
Answer

a.

The number of nodes in the tree is always at least the number of nodes on the longest path in
the tree.

b.

The number of NIL pointers in the tree is always greater than the number of nodes in the tree.

c.

Each terminal node in the tree is always at the end of a path that is as least as long as any o

Question

Suppose a binary tree is implemented as a linked structure in which each node contains both a left and right child pointer, either of which can be null or point to a node. Which of the following statements is false for this structure?
 Answer 




a.


The number of nodes in the tree is always at least the number of nodes on the longest path in 
the tree.
 




b.


The number of NIL pointers in the tree is always greater than the number of nodes in the tree.
 




c.


Each terminal node in the tree is always at the end of a path that is as least as long as any o

anonymous · Answer

While 'b' looks clearly false, i think you have inadvertently left 'c' incomplete.
'b' is false because in the case of a binary tree, all leaf nodes will contain NULL pointers, and the number of leaf nodes in a binary tree will always be less than the actual no. of nodes.

rsmith6559 · Answer

Always is such a strong word.  A BST with only a root node has the same number of nodes as leaf nodes.

Anyway, the test cases that I counted out B is actually true.  In a balanced tree, if the depth is x, the number of nodes would be 2**x - 1.  The width would be ( 2**x ) / 2, which when multiplied by the two NILs that a leaf node has would be 2**x.  On an unbalanced tree, one NIL would appear on each node except a leaf node having two NILs.