BINARY TREES

Question 1

Define and illustrate a tree

Answer 1

•A tree (in data structure terms)
is defined as a structure in which a set of nodes are connected together by their edges, in a parent-child relationship.

*See notes for pic

Question 2

What are the different applications of tree structures

Answer 2

• Databases
• File systems
• Web sites

Question 3

What are the characteristics of trees

Answer 3

• Consists of nodes connected by edges.
• Edges between the nodes represent the way the nodes are
related.
• The only way to get from node to node is to follow a path
along the edges.

Question 4

What is a rooted tree

Answer 4

•A rooted tree is one where there is one distinguished node called the root, and every other node is connected to only one parent.

Question 5

What is binary tree?

Answer 5

•A binary tree is one in which each node has at most two children, each called the left and right child.

Question 6

Describe the following terminologies: path root and parent

Answer 6

• Path: Traversal from node to node along the edges results in a
sequence called path.
• Root: Node at the top of the tree.
• Parent: Any node, except root has exactly one edge running
upward to another node. The node above it is called parent.

Question 7

Describe the following terminologies: child, lead and subtree

Answer 7

• Child: Any node may have one or more lines running
downward to other nodes. Nodes below are children.
• Leaf: A node that has no children.
• Subtree: A subtree of a tree, rooted at a particular node, is a tree consisting of that node and all its descendants.

Question 8

Describe the following terminologies: external, internal node, siblings, ancestor and descendant

Answer 8

• Nodes with the same parent are called siblings
• An external (leaf, or terminal) node has no children
• An internal (non-terminal) node has one or more children
• If there is a path from node A to node B, then A is an ancestor of B, and B is a
descendant of A.

Question 9

Describe the following terminologies: visiting, traversing, levels and keys

Answer 9

• Visiting: A node is visited when program control arrives at the
node, usually for processing.
• Traversing: To traverse a tree means to visit all the nodes in
some specified order.
• Levels: The level of a particular node refers to how many
generations the node is from the root. Root is assumed to be
level 0.
• Keys: Key value is used to search for the item or perform
other operations on it.

Question 10

Describe the depth height and size of a tree

Answer 10

• The depth of a node is the length of the path from the root to the node (The root has a depth of 0.)
• The height of a node is the length of the path from the node to the deepest leaf.
• The size of a node is the number of
nodes in the subtree rooted at that node (including itself.)

*See notes for illustration

Question 11

What is the difference between a general tree and a binary tree

Answer 11

• A general tree is a data structure in that each node can
have infinite number of children.
• Every node in a binary tree can have at most two
children

Question 12

Define a balanced binary/AVL tree

Answer 12

A binary tree is balanced if and only if, for every node, the height of its left and right subtree differ by at most 1.

*See notes for illustration

Question 13

Define a binary search tree

Answer 13

This is a binary tree in which the left child is always less

that its parent, while right child is greater than its parent.

Question 14

What are the two ways of representing trees

Answer 14

1.Linked list
• Similar to Linked List but with two Links
• Store the nodes at unrelated locations in memory and
connect them using references in each node that point to its
children.

2.Arrays
• Can also be represented as an array, with nodes in specific
positions stored in corresponding positions in the array.

*See notes for illustrations

Question 15

What are different ways to traverse a tree

Answer 15

– Inordertraversal: Left subtree, Node, Right subtree
– Preordertraversal: Node, Left subtree, Right subtree
– Postordertraversal: Left subtree, Right subtree, Node

Question 16

Using relevant examples, distinguish between linear and non-linear data structures

Answer 16

In a linear data structure, data elements are arranged in a linear order where each and every element is attached to its previous and next adjacent eg arrays stacks and queues while in a non-linear data structure, data elements are attached in hierarchically manner eg
trees and graphs.

Question 17

Write the different algorithms for the different traversals

Answer 17

*See EDNAH CHAT for link

Question 18

Discuss any application of binary search trees in real life programming.

Answer 18

BSTs are used for indexing and multi-level indexing.
They are also helpful to implement various searching algorithms.
It is helpful in maintaining a sorted stream of data.
TreeMap and TreeSet data structures are internally implemented using self-balancing BSTs

Question 19

List and explain any three applications of the tree data structure in computing technology.

Answer 19

Store hierarchical data, like folder structure, organization structure, XML/HTML data.
Binary Search Tree is a tree that allows fast search, insert, delete on a sorted data. It also allows finding closest item
Heap is a tree data structure which is implemented using arrays and used to implement priority queues

Question 20

Discuss how space and time is understood and studied in computing in relation to algorithms

Answer 20

Space complexity :

Space complexity is defined as the process of determining a formula for the production of how much memory space will be required for the successful execution of an algorithm. The memory space we consider is the space of primary memory.

Time complexity :

The time complexity is defined as the process of determining a formula for total time required towards the execution of that algorithm. This calculation will be independent of implementation details and programming language.