Tree structure question


I need help solving this tree structure question:



Last edited on
> first child, next sibling structure
¿don't you think that perhaps it would be helpful to explain what does that mean? we are not in your class.

> How would you find the number of nullpointers?
count them. they don't appear magically, they are related to the nodes of the tree (inner nodes or leaves)
¿when would a node have a nullpointer? (¿and why?)
¿don't you think that perhaps it would be helpful to explain what does that mean? we are not in your class.

https://en.wikipedia.org/wiki/Left-child_right-sibling_binary_tree
then it's easy, each node have two linked list.
¿how many nullpointers have a linked list? none, because the implementation makes it circular.
For the the first child, next sibling tree

a. every node contains a value and two pointers: a pointer to the first child, and a pointer to the next sibling. In a tree containing n nodes, total number of pointers == n*2

b. every node (except the root) has exactly one pointer pointing to it: it is either a first child or a next sibling. In a tree containing n nodes, the total number of non-null pointers == n-1

From a. and b. the total number of null pointers == n*2 - (n-1) == n+1
Last edited on
@JLBorges
In your 3rd step I don't get how you could make that arithmetic to get n. Plus why wouldn't it be 2^n pointers, but n*2?

When you mean by n*2, is that the same thing as 2 times n or n to the power of 2?
Last edited on
Perhaps a picture would help.

See the picture at he bottom of this page under '2. Left Child - Right Sibling Representation'
http://btechsmartclass.com/DS/U3_T2.html
Picture: http://btechsmartclass.com/DS/images/Left%20Child%20Right%20Sibling.png

In the diagram, each node has three fields: a value (at the top) and and two pointers (in the bottom two cells)
In the left cell at the bottom is the pointer to the first (left) child; and the right cell has the pointer to the next (right) sibling.
A non-null pointer is indicated by an arrow pointing away from the cell, and a null-pointer is marked as NULL.

There are eleven nodes in the tree: A, B, C, D, E, F, G, H, I, J, K n == 11

a. Total number of pointers == total number of cells at the bottom == n*2 == 11*2 == 22

b. Number of non-null pointers == n-1 == 11-1 == 10
(There is one pointer pointing to every node except for the root node.)

c. The total number of null pointers == total number of pointers - number of non-null pointers
== (n*2) - (n-1) == (n+n) - (n-1) == n+n-n+1 == n+1 == 11+1 == 12 == 22-10
Last edited on
Registered users can post here. Sign in or register to post.