Trees Find a tree diagram, above, that is NOT a binary search tree. Explain why

Question

Trees Find a tree diagram, above, that is NOT a binary search tree. Explain why it is not. Trees 2 and 3 look something like min-heap. One is, one is not. Which one is not? Explain why. Is tree 4, above, balanced? If not, why not? If so, add one node to make it unbalanced. Write down the values of the nodes in tree 3, in the order that a breadth-first search would visit them. If you start with a binary search tree with 30 elements in it, and delete the minimum element 10 times, the resulting tree will have a bad property. Explain what this property is and why it will occur.

Explanation / Answer

a. Find a tree diagram, above, that is not a binary search tree. Explain why it is not.
Binary search tree, is a tree which is allowed to have atmost 2 children for every node. And at any given node,
all the left children should be less than the node value, and all the right children should be greater than
the node value. For tree 2, the root value is 2, and the left child value is 3 which violates the
binary search tree rule.The same happens with tree3. Also with tree 4, 8 is a node which is on the right of 11.
Therefore tree1 is the only binary search tree.

b. A min heap is the one that at any given node, the children should be greater than the root.
And there is no rule on the left and right child ordering. The other rule is that, the nodes
should be added to the tree in an ordered fashion, i.e., should be added at any given level from
left most node, till the possible right most node. And possibly all the levels except the last one
should be filled.
Tree2, till level 3, everything looks fine, but at the last level, before adding elements at the left
side positions i.e., 6, and 8, you should not add nodes to the parent 11.
Therefore, it violates a minheap rule.

c. A tree is said to be balanced if at every node, the balance i.e., the difference between the
left subtree height, and right subtree height should be within the range [-1, 1].
Coming to tree4, it is balanced. Whereas, if you add a node with some value as a child to
the node with value 6. It becomes unbalanced at node 17. This is because the difference between
the left subtree and right subtree at node 17 will then be 2.

d. The values of the nodes in tree 3, in BFS:
2, 3, 5, 8, 17, 6, 37, 11, 12.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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