Binary Search Tree/ CS Using the diagram above, answer each of the following que
ID: 3696663 • Letter: B
Question
Binary Search Tree/ CS
Using the diagram above, answer each of the following questions.
a)What is a leaf node? List the leaves in the tree above.
b)What are the Ancestors of a Node and list them for the Node containing 16.
c)What does it mean for nodes to be siblings? List all combinations of nodes that are siblings.
d)What is the root of a binary tree? In this example which node is the root?
e)What is the height of this binary tree?
f)What does it mean for a binary tree to be balanced? Is this tree balanced?
g)What does it mean for a binary tree to be complete? Is this tree complete?
h)What makes a binary tree a binary search tree? Is the tree above a binary search tree?
45 12 30 10 41 16 60Explanation / Answer
Answers
a) Leaf Node is a node which have no children. Generally, in a binary tree, a node can have atmost of 2 children termed as left child and right child. If, for a node, the left child and right child are not present, then that node is called leaf node. In the above tree, the leaf nodes are
16, 7, 10, 11, 60
b) Ancestors of a node are those nodes which lie in the upper levels of a current node. It can be explained as, the parent node of the current node, the parent node's parent node and so on until the top level is reached. In other words, we can say, if a node has children or subtrees, then that node can be termed as an ancestor node for all the nodes in its subtrees.
In the above tree, the ancestor nodes for node 16 are 30, 12, 45
c) Nodes are said to be sibblings if the parent node is the same for both the nodes.
In the above tree, the possible combination of sibbling nodes are
[30, 7] --> parent is 12
[10, 41] --> parent is 99
[3, 60] --> parent is 41
[12, 99] --> parent is 45
d) The root of the binary tree is defined as the node at level 0 or can be said as top most level, such that it has no parent node. A binary tree starts from the root node with left and right sub trees. In the above, tree 45 is the root node of the binary tree
e) Height of the binary tree is defined as the number of levels the tree extends downwards. It can be explained as the count of number of nodes passed downwards to reach the leaf node in the last level. The height of this tree is 5
h) A binary tree is said to be a binary search tree, if for any node, the values in the left subtree are less than the root node and values in the right subtree are greater than the root node. The above tree is not a binary search tree.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.