In this problem we consider binary trees, represented by pointer data structures. A binary tree is...

Transcribed Image Text:

In this problem we consider binary trees, represented by pointer data structures. A binary tree is either an empty tree or a node (called the root) made of a single integer value and two further binary trees, called the left subtree and the right subtree. For example, the figure below shows a binary tree that has six nodes. Its root contains the value 5, and the roots of its left and right subtrees have the values 3 and 10. The right subtree of the node with the value 10, as well as the left and right subtrees of the nodes with the values 1, 20 and 21, are empty trees. 20 A binary tree can be given using a pointer data structure. Assume that the following declaration are given: class Tree { 10 public int x; public Tree 1; public Tree r; }; An empty tree is represented by an empty pointer (denoted by null). A non-empty tree is represented by a pointer to an object representing its root. The attribute x holds the integer contained in the root, while attributes 1 and r hold the left and right subtrees of the binary tree. A path in a binary tree is a non-empty sequence of nodes that one can go through by following the pointers. The length of a path is the number of pointers it follows. More formally, a path of length K is a sequence of nodes P[0], P[1], ..., P[K], such that node P[I + 1] is the root of the left or right subtree of P[I], for 0 ≤ I < K. For example, the sequence of nodes with values 5, 3, 21 a path of length 2 in the tree from the above figure. The sequence of nodes with values 10, 1 is a path of length 1. The sequence of nodes with values 20, 3, 21 is not a valid path. The height of a binary tree is defined as the length of the longest possible path in the tree. In particular, a tree of only one node has height 0 and an empty tree has height -1. For example, the tree shown in the above figure is of height 2. A binary tree T is given. A node of tree T containing value V is described as visible if the path from the root of the tree to that node does not have a node with any value exceeding V. In particular, the root is always visible and nodes with values lower than that of the root are never visible. In this problem we consider binary trees, represented by pointer data structures. A binary tree is either an empty tree or a node (called the root) made of a single integer value and two further binary trees, called the left subtree and the right subtree. For example, the figure below shows a binary tree that has six nodes. Its root contains the value 5, and the roots of its left and right subtrees have the values 3 and 10. The right subtree of the node with the value 10, as well as the left and right subtrees of the nodes with the values 1, 20 and 21, are empty trees. 20 A binary tree can be given using a pointer data structure. Assume that the following declaration are given: class Tree { 10 public int x; public Tree 1; public Tree r; }; An empty tree is represented by an empty pointer (denoted by null). A non-empty tree is represented by a pointer to an object representing its root. The attribute x holds the integer contained in the root, while attributes 1 and r hold the left and right subtrees of the binary tree. A path in a binary tree is a non-empty sequence of nodes that one can go through by following the pointers. The length of a path is the number of pointers it follows. More formally, a path of length K is a sequence of nodes P[0], P[1], ..., P[K], such that node P[I + 1] is the root of the left or right subtree of P[I], for 0 ≤ I < K. For example, the sequence of nodes with values 5, 3, 21 a path of length 2 in the tree from the above figure. The sequence of nodes with values 10, 1 is a path of length 1. The sequence of nodes with values 20, 3, 21 is not a valid path. The height of a binary tree is defined as the length of the longest possible path in the tree. In particular, a tree of only one node has height 0 and an empty tree has height -1. For example, the tree shown in the above figure is of height 2. A binary tree T is given. A node of tree T containing value V is described as visible if the path from the root of the tree to that node does not have a node with any value exceeding V. In particular, the root is always visible and nodes with values lower than that of the root are never visible.

Answer rating: 100% (QA)

To solve the problem we can use a recursive approach to traverse the binary tree and determine which ... View the full answer