Define the left child of node n in a binary tree. What are the three properties

Question

1. Define the left child of node n in a binary tree.
2. What are the three properties of each node n in a binary search tree?
3. In what order does a preorder traversal visit a node and its subtrees?
4. In what order does an inorder traversal visit a node and its subtrees?
5. In what order does a postorder traversal visit a node and its subtrees?
6. In an array-based representation of a binary tree, what is the purpose of a free list?
7. What is a search key?
8. Define an n-ary tree.
9. Describe the STL functions lower_bound and upper_bound.

Explanation / Answer

1.A binary tree is made of nodes, where each node contains a "left" reference, a "right" reference, and a data element. Node at Left refernce is call left child.

2.

a) Each node has no more than two child nodes.

b)The left subtree of a node contains only nodes with keys less than the node's key.

c) The right subtree of a node contains only nodes with keys greater than the node's key.

6) Sorry Im not sure

7)Search key is the thing you are searching for in a collection of data.

8)A n-ary tree is a rooted tree in which each node has no more than n children. It is also sometimes known as a k-way tree, an N-ary tree, or an M-ary tree. A binary tree is the special case where n=2.

9)

Return iterator to lower bound

Returns an iterator pointing to the first element in the range [first,last) which does not compare less than val.

The elements are compared using operator< for the first version, and comp for the second. The elements in the range shall already be sorted according to this same criterion (operator< or comp), or at least partitioned with respect to val.

The function optimizes the number of comparisons performed by comparing non-consecutive elements of the sorted range, which is specially efficient for random-access iterators.

Return iterator to upper bound

Returns an iterator pointing to the first element in the container whose key is considered to go after k.

The function uses its internal comparison object (key_comp) to determine this, returning an iterator to the first element for which key_comp(k,element_key) would return true.

If the map class is instantiated with the default comparison type (less), the function returns an iterator to the first element whose key is greater than k.

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.