0
Still curious? Ask our experts.
Chat with our AI personalities
Lao
Steve
Jordan
Add your answer:
Earn +20 pts
How many leaf nodes does the full binary tree of height h 3 have?
For a full binary tree of height 3 there are 4 leaf nodes. E.g., 1 root, 2 children and 4 grandchildren.
A full binary tree with n nonleaves contains how many nodes?
Convert n to a binary value, then set the next most significant bit. For instance, if there are 7 non-leaves, this equates to 00000111 in binary. Each bit tells us how many non-leaves exist in each level, where the least-significant bit (bit 0) represents the root node and the most-significant bit (bit 2) represents the lowest level. Thus we have 1+2+4=7 non-leaf nodes in total. The next most-significant bit (bit 3) represents the leaf nodes and if we set that bit we get 00001111, which is 15 decimal. Thus there are 15 nodes in total. We can visualise this binary tree using hexadecimal notation: 1 2 3 4 5 6 7 8 9 a b c d e f (Note: 0xf = 15 decimal). Using binary notation, we get the following: 1st level (bit 0) = 00000001 = 1 non-leaf node (the root) 2nd level (bit 1) = 00000010 = 2 non-leaf nodes 3rd level (bit 2) = 00000100 = 4 non-leaf nodes 4th level (bit 3) = 00001000 = 8 leaf nodes Thus we get: 00000001+00000010+00000100+00001000=00001111 Or, in decimal: 1+2+4+8=15
When we insert a new node in a binary search tree will it become an internal node or terminal node?
It will be come a terminal node. Normally we call terminal nodes leaf nodes because a leaf has no branches other than its parent.
Is null node equal to leaf node?
No. A leaf node is a node that has no child nodes. A null node is a node pointer that points to the null address (address zero). Since a leaf node has no children, its child nodes are null nodes.
What is the difference between extended binary tree and a binary search tree?
A strictly binary tree is one where every node other than the leaves has exactly 2 child nodes. Such trees are also known as 2-trees or full binary trees. An extended binary tree is a tree that has been transformed into a full binary tree. This transformation is achieved by inserting special "external" nodes such that every "internal" node has exactly two children.
