Binary trees

Question 1

Node

Answer 1

A node is a fundamental part of a tree. It can have a name, which we call the key. A node may also have additional information. We call this additional information the value or payload. While the payload information is not central to many tree algorithms, it is often critical in applications that make use of trees.

Question 2

Edge

Answer 2

An edge is another fundamental part of a tree. An edge connects two nodes to show that there is a relationship between them. Every node (except the root) is connected by exactly one incoming edge from another node. Each node may have several outgoing edges.

Question 3

Root

Answer 3

The root of the tree is the only node in the tree that has no incoming edges. In Figure 2, / is the root of the tree.

Question 4

Path

Answer 4

A path is an ordered list of nodes that are connected by edges.

Question 5

Children

Answer 5

The set of nodes that have incoming edges from the same node are said to be the children of that node.

Question 6

Parent

Answer 6

A node is the parent of all the nodes it connects to with outgoing edges.

Question 7

Sibling

Answer 7

Nodes in the tree that are children of the same parent are said to be siblings.

Question 8

Si tree

Answer 8

A subtree is a set of nodes and edges comprised of a parent and all the descendants of that parent.

Question 9

Leaf Node

Answer 9

A leaf node is a node that has no children.

Question 10

Level

Answer 10

The level of a node n is the number of edges on the path from the root node to n.

Question 11

Height

Answer 11

The height of a tree is equal to the maximum level of any node in the tree.

Question 12

BinaryTree()

Answer 12

BinaryTree() creates a new instance of a binary tree.

Question 13

get_root_val()

Answer 13

get_root_val() returns the object stored in the current node.

Question 14

set_root_val(val)

Answer 14

set_root_val(val) stores the object in parameter val in the current node.

Question 15

get_left_child()

Answer 15

get_left_child() returns the binary tree corresponding to the left child of the current node.

Question 16

get_right_child()

Answer 16

get_right_child() returns the binary tree corresponding to the right child of the current node.

Question 17

insert_left(val)

Answer 17

insert_left(val) creates a new binary tree and installs it as the left child of the current node.

Question 18

insert_right(val)

Answer 18

insert_right(val) creates a new binary tree and installs it as the right child of the current node.